Hidden Services Protocol for Mixnets

Hidden Services Protocol for Mixnets Nicolas Constantinides∗

Mahdi Rahimi

Stavros Nonis

Unaffiliated

COSIC, KU Leuven Leuven, Belgium

Unaffiliated

arXiv:2609.01326v1 [cs.CR] 1 Sep 2026

Abstract

global adversary that observes every network link. This protection arises because each packet traverses an independently selected sequence of intermediaries, called mixnodes, which randomly delay and cryptographically transform packets before forwarding them, making input–output traffic correlation challenging [24]. In this work, we focus on Loopix-like mixnets [22], in which mixnodes are partitioned into layers and each mixnode forwards packets only to mixnodes in subsequent layers. Each mixnode provides mixing by delaying received packets for a random interval sampled according to the stop-and-go mixing mechanism [16]. Loopix builds on the Sphinx packet format [5], which provides constant-size, layered-encrypted packets whose headers contain hop-by-hop forwarding instructions and whose payloads carry application data. To resist traffic analysis, Loopix generates packets through two independent streams: a loop cover traffic stream, consisting of dummy packets sent by Loopix users that eventually return to them, and a real traffic stream, which sends queued application packets when available and otherwise transmits additional loop cover traffic at the same rate. Because both streams are scheduled independently of whether application data are available, the observable transmission pattern does not reveal when a user has real messages to send, thereby providing unobservability. Nym [6] operationalizes the Loopix design using a five-stage topology consisting of entry gateways, three mix layers, and exit gateways. The three mix layers perform the mixing functionality of Loopix, while the entry and exit gateways act as interfaces between users and the mixnet. In particular, each user persistently connects to a single entry gateway, which serves as their long-term entry point into the mixnet. Beyond one-way anonymous messaging from a sender to a receiver, Nym supports Single-Use Reply Blocks (SURBs). A SURB allows a party that wishes to receive replies—the SURB creator—to provide another party—the replier—with a disposable return path, enabling the replier to respond without learning the creator’s identity or the gateways and mixnodes traversed by the return path. The intended anonymity is therefore one-sided: the creator’s location remains hidden from the replier, while the reply must still enter the mixnet through an entry gateway. To construct this return path, the creator precomputes a unique routing token, represented by a Sphinx reply header, together with per-hop encryption secrets for each mixnode on the path and a separate key for protecting the application payload. The creator then provides this information to the replier. To send a reply, the replier first encrypts the application content using the reply key, then prepends a replier-generated acknowledgment SURB together with a small amount of metadata. The packet is subsequently processed using the per-hop secrets such that, as it traverses the return path, each mixnode removes the corresponding encryption layer. By the time the packet reaches the creator’s gateway, the outer layers have been removed. The gateway can then extract the acknowledgment SURB and reinject it into the mixnet to support reliable delivery,

Mix networks (mixnets) provide network-level privacy by routing each communication packet through a sequence of intermediaries, called mixnodes, that randomly delay and cryptographically transform packets before forwarding them, making it difficult for observers to link mixnet entries to exits. While this mechanism protects sender privacy from both external adversaries and the receiver, existing mixnets lack a secure and practical protocol that simultaneously protects receiver (destination) privacy, particularly from the sender. We close this gap. We introduce the first practical and secure hidden-service protocol for mixnets, providing receiver privacy alongside sender anonymity. Our design builds on Single-Use Reply Blocks (SURBs), which enable anonymous replies without revealing the receiver’s address. We show, however, that existing approaches to using SURBs expose two practical attacks that can compromise sender or receiver anonymity when the opposing party controls only a single mixnode. We develop defenses against both vulnerabilities. Building on these defenses, we introduce NymHS, a secure and practical hidden-service protocol for mixnets that supports anonymous service discovery, authenticated bidirectional sessions, and asynchronous SURB replenishment. We implement NymHS on the open-source Nym codebase and evaluate its practicality through web-browsing experiments across 118 websites, measuring each of the 27 configurations three times (9,558 page loads). Our results demonstrate that hidden services can be deployed efficiently over mixnets. In particular, increasing the Sphinx payload from 2 KiB to 10 KiB reduces mean page-load latency by approximately 5.2× and decreases communication overhead from 21.7% to 4.3% relative to the current Nym baseline.

Keywords Anonymous communication, Mix networks, Hidden services

1

Introduction

The Internet Protocol inherently exposes communication metadata—who communicates with whom, when, and how often— even when payloads are encrypted, as encryption protects only the content of communications [6]. Anonymous communication networks aim to protect this metadata [2, 4, 6, 29, 33]. Among these systems, mix networks (mixnets) [2, 6, 8, 18, 22, 25–27, 32] provide some of the strongest privacy guarantees, even against a passive ∗ Corresponding author.

This work is licensed under the Creative Commons Attribution 4.0 International License. To view a copy of this license visit https://creativecommons.org/licenses/by/4.0/ or send a letter to Creative Commons, PO Box 1866, Mountain View, CA 94042, USA. Proceedings on Privacy Enhancing Technologies YYYY(X), 1–20 © 2026 Copyright held by the owner/author(s). 1

Proceedings on Privacy Enhancing Technologies YYYY(X)

Constantinides et al.

while the application content remains encrypted under the reply key and can be decrypted only by the creator. Although SURBs are deployed in the Nym mixnet, their current design introduces anonymity risks for both communicating parties. First, because the routing token associated with a SURB is unique and known to the SURB creator in advance, a malicious creator can construct the return path so that a mixnode under their control serves as its first mix hop and then monitor that mixnode for the corresponding token. Observing the token reveals which gateway injected the reply, thereby exposing the replier’s long-term entry gateway. Conversely, Nym provides the replier with all per-hop payloadkey seeds associated with the SURB. A malicious replier that also controls the mixnode serving as the final hop of the return path can therefore identify the corresponding reply by deriving the payload transformation expected at that hop and matching it against the observed packet. This reveals the creator’s long-term entry gateway (Section 3). In both cases, discovering the victim’s gateway is decisive: once the adversary learns the victim’s long-term entry gateway, deanonymization no longer requires compromising the entire mix path, but instead reduces to compromising or flooding that gateway. Beyond the vulnerabilities in the current deployment of SURBs, a second limitation is the absence of hidden services for mixnets. Currently, contacting a Nym application typically requires either prior knowledge of its network address or the use of a long-lived nickname tied to a fixed entry gateway, allowing that gateway to associate the nickname with the underlying user (Section 7). A hidden service, by contrast, keeps both the client and the service location hidden while eliminating the need to know the receiver’s exact network address in advance, a property that is particularly important for applications such as anonymous feedback and whistleblowing [19]. We address these vulnerabilities and limitations. First, to enable secure SURB-based communication, we introduce a new protocol that does not expose mix-derived payload-key seeds to the replier. Instead, the prior-hop seeds are embedded within the layeredencrypted final routing block, where only the creator’s gateway can recover them. The gateway can then reverse the cryptographic transformations applied by the mixnodes, extract the acknowledgment SURB, and inject it back into the mixnet, while preventing the final mix hop from recognizing the reply using disclosed secrets or predicted ciphertext. Second, we introduce replier-anonymous SURBs, which conceal the creator’s precomputed routing token inside an outer Sphinx packet and reveal it only at a designated swap hop. Consequently, a malicious creator monitoring the first mix hop of the inner route observes traffic arriving from the swap path rather than directly from the replier’s gateway. Building on these primitives, we third design and implement NymHS, the first hidden-service protocol for the Nym mixnet, providing authenticated publication, anonymous discovery, pseudonymous bidirectional sessions, and asynchronous SURB replenishment, with both control and application traffic routed entirely through the mixnet. Fourth, we extend the open-source Nym codebase to implement our hidden-service protocol and evaluate NymHS through static web browsing across 118 websites under 27 configurations—nine

Sphinx payload sizes by three rewrap depths—each repeated three times, for 9,558 page loads. Our performance evaluation shows that increasing the Sphinx payload from 2 KiB to 10 KiB reduces mean page-load latency by approximately 5.2× and payload overhead from 21.7% to 4.3%, while increasing the rewrap depth adds only 0.3–0.6 s of latency (Section 6). In particular, our contributions are as follows. • We analyze the security of Nym SURB replies and their use for acknowledgment-based reliability (Section 2.2). • We identify first-mix-hop and last-mix-hop attacks that expose the replier’s or creator’s gateway when the adversary controls only a single mixnode, and demonstrate their impact on Nym applications (Sections 3 and 7). • We prevent last-mix-hop matching by withholding mixderived payload-key seeds from the replier and embedding them for recovery by the creator’s gateway (Section 5.1). • We introduce Sphinx-compatible replier-anonymous SURBs that prevent first-mix-hop header matching (Section 5.2). • We design and implement NymHS, the first hidden-service protocol for mixnets built on these defenses (Section 5.3). • We evaluate NymHS across varying payload sizes and rewrap depths, showing that larger payloads substantially reduce fragmentation overhead while replier anonymity incurs only modest additional latency (Section 6). Roadmap. Section 2 reviews Loopix, Nym, and SURBs; Section 3 presents the identified attacks; Sections 4–5 develop NymHS and analyze its security properties; Section 6 reports the experimental evaluation; and Section 7 discusses related work.

2

Background

This section reviews the Nym mixnet architecture, the Sphinx packet format, and its SURB construction. For a more detailed representation of the Sphinx packet format, please refer to Appendix A.

2.1

Nym Mixnet Architecture

Nym is a Loopix-like mixnet organized into five layers: an entrygateway layer, three mix layers, and an exit-gateway layer. The gateway layers serve as interfaces between users and the mixnet without performing mixing, while the three intermediate layers constitute the core mixnet and perform the transformations required to anonymize traffic. In particular, entry gateways authenticate users, verify whether they are authorized to access the system, and, if so, inject their traffic into the mixnet; importantly, they do not perform Sphinx packet processing. Sphinx processing is instead performed by the remaining four layers. Each of the three mix layers removes one Sphinx layer, recovers the next forwarding hop, and randomly delays the packet to provide mixing. The exit gateway removes the final Sphinx layer, delivers the message1 to its destination, sends acknowledgments back to the sender through the mixnet, and may buffer traffic for offline users. An important design feature of Nym is that each user persistently connects to a single entry gateway, which serves as that user’s long-term point of presence in the network. The gateway also temporarily stores packets destined for offline clients and forwards them when the clients reconnect. Discovering this gateway 1We use the terms packet and message interchangeably throughout this paper.

2

...

Proceedings on Privacy Enhancing Technologies YYYY(X)

is therefore particularly consequential for deanonymization: once a user’s long-term attachment point is known, the adversary can target that gateway directly rather than having to infer the complete route traversed by the user’s messages to associate the client with its communication. In Nym, messages are transmitted using fixed-size Sphinx packets [5], each of which is routed independently through the mix layers. Packets belonging to the same communication may therefore traverse different routes, making end-to-end traffic correlation more difficult for a network adversary. At each mix layer, the corresponding mixnode removes one cryptographic layer, learns only the next forwarding hop, and applies a sender-selected delay drawn from an exponential distribution with mean 𝜇 = 50 ms [20].2 Following Loopix, Nym senders maintain two independent traffic streams [22]. On the real traffic stream, transmission opportunities occur according to a Poisson process with a mean inter-departure time of 20 ms. At each opportunity, the sender transmits the headof-line application packet if the queue is non-empty and otherwise emits a loop cover packet. A separate loop cover traffic stream generates additional dummy packets that eventually return to their sender, with a mean inter-departure time of 200 ms at both clients and mixnodes [20]. Because both streams operate independently of whether application data are queued, a passive observer cannot readily infer when a user is transmitting real traffic.

2.2

where 𝑚𝑖 contains per-hop routing metadata, including the forwarding delay and a flag, |𝑚𝑖 ∥𝑛𝑖+1 ∥𝛾𝑖+1 | = 𝜂, and |𝛽𝑖+1 | = 𝑟𝜂. ℎ (𝛼 ,𝑠 ) The mixnode then reblinds the group element as 𝛼𝑖+1 = 𝛼𝑖 𝑏 𝑖 𝑖 , −1 removes one payload layer as 𝛿𝑖+1 = 𝜋𝑘 𝜋 (𝛿𝑖 ), and forwards 𝑖

(𝛼𝑖+1, 𝛽𝑖+1, 𝛾𝑖+1, 𝛿𝑖+1 ) to 𝑛𝑖+1 . The final hop performs the corresponding processing without introducing an additional delay, recovers the inner payload and its destination, and forwards the message accordingly. SURBs extend Sphinx to support anonymous replies [5]. A SURB is defined as
S = 𝑛 0, , 𝑀0, , 𝜎0, . . . , 𝜎 𝜈 −1, , 𝑘˜ , where 𝑀0 is a precomputed Sphinx header for the first mix hop 𝑛 0 , 𝜎0, . . . , 𝜎 𝜈 −1 are the payload-key seeds associated with a reply route of length 𝜈, and 𝑘˜ ∈ {0, 1}𝜅 is an independent reply-encryption key rather than a seed. Upon receiving the SURB, the replier derives each 𝑘𝑖𝜋 from the supplied seeds as described above and uses 𝑘˜ exclusively to encrypt the application-layer reply.3 Each reply fragment consumes one SURB: the replier constructs 𝛿 0 using the ˜ injects (𝑀0, 𝛿 0 ) at 𝑛 0 , and can send the reply supplied seeds and 𝑘, without learning the recipient’s identity or complete return route. SURB Transmission. Because SURBs are single-use, a fragmented reply consisting of 𝑛 pieces requires a pool {S1, . . . , S𝑛 } with ) ˜
S𝑖 = 𝑛 0(𝑖 ) , 𝑀0(𝑖 ) , 𝜎0(𝑖 ) , . . . , 𝜎 𝜈(𝑖−1 , 𝑘𝑖 .

Sphinx and SURB-Based Replies

The replier’s complete message is divided into fragments {𝑓1, . . . , 𝑓𝑛 }; each fragment 𝑓𝑖 carries a marshaled fragment header FH𝑖 containing a set identifier sid, the fragment count 𝑛, the fragment index 𝑖, and an optional successor-set link when a message spans more than 255 fragments. For each 𝑖, the replier constructs a delivery-confirmation packet SURB-ACK𝑖 over a fresh acknowledgment route and forms 𝑝𝑖 = SURB-ACK𝑖 ∥𝐻 (𝑘˜𝑖 )∥EncAES (FH𝑖 ∥𝑓𝑖 ),

Nym relies on the Sphinx packet format [5], which provides constant-size packets and layered anonymous routing with packet indistinguishability, replay protection, and bitwise unlinkability between hops. A Sphinx packet consists of a header and a payload. The header received at hop 𝑖 is 𝑀𝑖 = (𝛼𝑖 , 𝛽𝑖 , 𝛾𝑖 ), where 𝛼𝑖 is an ephemeral Diffie–Hellman group element, 𝛽𝑖 is an encrypted routing block, and 𝛾𝑖 is a header-integrity tag; the accompanying payload ciphertext is denoted by 𝛿𝑖 . To maintain a fixed packet size, Sphinx pads headers and payloads when necessary. We denote by Pad𝜋 the Sphinx padding operation to a fixed payload length and by 𝜋𝑘 the keyed payload permutation under key 𝑘. Sphinx additionally relies on several key-derivation functions, a routing-block stream cipher, an integrity MAC, a blinding map, and size parameters (𝜂, 𝑟, 𝜅), which we detail in Appendix A.1; the complete Sphinx header construction is provided in Appendix A.2.

𝑘˜𝑖

where 𝐻 (𝑘˜𝑖 ) is a key digest that allows the creator’s client to later locate 𝑘˜𝑖 and decrypt FH𝑖 ∥𝑓𝑖 . The replier pads 𝑝𝑖′ = Pad𝜋 (𝑝𝑖 , ℓ) to the Sphinx payload size ℓ and applies the payload transformations 𝛿 0(𝑖 ) = 𝜋𝑘 𝜋,(𝑖 ) ◦ · · · ◦ 𝜋𝑘 𝜋,(𝑖 ) (𝑝𝑖′ ) 0

Sphinx Processing. We model ℎ𝜏 , ℎ 𝜇 , ℎ 𝜌 , ℎ𝑏 , and ℎ𝜎 as randomoracle hash functions. Under this model, upon receiving (𝑀𝑖 , 𝛿𝑖 ), mixnode 𝑛𝑖 along the packet’s route uses its private key 𝑥𝑛𝑖 to 𝑥𝑛

and delivers the remaining ciphertext to the client; missing acknowledgments trigger retransmission using a fresh SURB. Once online, the client matches 𝐻 (𝑘˜𝑖 ) against its stored keys, recovers 𝑘˜𝑖 , and decrypts the fragment.

?

compute the Diffie–Hellman shared secret 𝑠𝑖 = 𝛼𝑖 𝑖 , verifies 𝛾𝑖 = 𝜇 (ℎ 𝜇 (𝑠𝑖 ), 𝛽𝑖 ), and aborts if verification fails. To prevent replay attacks, it also derives the replay tag 𝜏𝑖 = ℎ𝜏 (𝑠𝑖 ) and drops the packet if 𝜏𝑖 has already been observed; otherwise, it records 𝜏𝑖 , preventing the same header from being processed twice. The mixnode then derives the routing-mask stream 𝜌𝑖 = 𝜌 (ℎ 𝜌 (𝑠𝑖 )), the payload-key seed 𝜎𝑖 = ℎ𝜎 (𝑠𝑖 ), and the payload key 𝑘𝑖𝜋 = ℎ k (𝜎𝑖 ). Extending 𝛽𝑖 by one routing-block step and removing the corresponding mask reveals the next-hop information: 𝛽𝑖′ = 𝛽𝑖 ∥0𝜂 ,

𝜈 −1

) under the keys derived from 𝜎0(𝑖 ) , . . . , 𝜎 𝜈(𝑖−1 . It then sends (𝑀0(𝑖 ) , 𝛿 0(𝑖 ) ) (𝑖 ) to 𝑛 0 . The recipient gateway forwards SURB-ACK𝑖 into the mixnet

Design rationale. In the original Sphinx SURB [5], the replier receives the precomputed header together with the single reply ˜ mix-derived payload keys are not disclosed. Nym instead key 𝑘; includes every seed 𝜎0, . . . , 𝜎 𝜈 −1 so that, when the reply reaches the creator’s gateway, the mix-derived payload layers can be reversed while the application ciphertext protected under 𝑘˜ remains sealed. The gateway can then extract the embedded SURB-ACK and send it back to the replier, confirming that the packet was received even

𝑚𝑖 ∥𝑛𝑖+1 ∥𝛾𝑖+1 ∥𝛽𝑖+1 = 𝛽𝑖′ ⊕ 𝜌𝑖 ,

3 The requester supplies SURBs before any reply is transmitted; applications that

2 Detailed Sphinx header and payload formats are provided in Appendix A.

exchange SURBs are discussed in Section 7. 3

Proceedings on Privacy Enhancing Technologies YYYY(X)

Constantinides et al.

˜ when the receiver is offline and the 𝑘-protected fragment must be buffered until the client reconnects. This separation therefore enables reliable communication with offline receivers: the gateway can return the SURB-ACK while buffering the sealed fragment for subsequent delivery. However, disclosing the mix-derived seeds to the replier also introduces the vulnerabilities discussed in Section 3.

3

appear at the controlled hop. The malicious mixnode can then directly match the observed payload against this predicted ciphertext. Second, the malicious mixnode derives the payload-key seed 𝜎𝑖 = ℎ𝜎 (𝑠𝑖 ) from its Diffie–Hellman shared secret with the packet and compares it against the seeds supplied in the SURB. Either method uniquely identifies the reply and reveals its next hop, namely the creator’s gateway. Unlike in the first-mix-hop attack, the malicious replier cannot choose which mixnode in the last layer is selected, as Nym selects this node uniformly from roughly 40 candidates. Nevertheless, application messages commonly consume many independently routed SURBs, one for each fragment. Consequently, even an adversary controlling only one last-layer mixnode obtains repeated opportunities to observe and recognize a reply, making the attack practical over repeated communication.

Problem Statement and Malicious SURB Path Attacks

Standard SURBs enable anonymous replies, but they do not protect endpoint anonymity when either the SURB creator or the replier is malicious and additionally controls a single mixnode. To characterize this limitation, we first define our threat model and then present two attacks—the first-mix-hop and last-mix-hop attacks—that expose a user’s gateway. We subsequently discuss the consequences of gateway discovery and formulate the design problem that motivates our defenses.

Gateway compromise. Once either attack reveals a user’s gateway, an adversary that subsequently compromises that gateway can deanonymize the attached client. A compromised gateway observes every delivered fragment and can associate the client’s IP address ˜ Because the replier alwith the corresponding binding tag 𝐻 (𝑘). ˜ it can match this value against the gateway’s ready knows 𝐻 (𝑘), records and identify the intended recipient. Such compromise need not rely on exploiting the gateway’s software: bribery [15], coercion, or legal compulsion may provide equivalent access. Thus, an adversary with comparatively limited capabilities—a malicious user, control of a single mixnode, and subsequent access to the identified gateway—can ultimately deanonymize a communicating endpoint.

Threat model. We adopt Nym’s infrastructure-aware threat model [6]. In particular, our design considers (1) a computationally bounded global passive adversary (GPA) capable of observing traffic across all network links, (2) a mixnode adversary that operates malicious mixnodes, (3) an adversary that controls a subset of the gateways, and (4) a malicious user that additionally controls a single mixnode.4 Malicious first-mix-hop attack. The first attack combines a malicious SURB creator with a mixnode under the creator’s control, which the creator deliberately selects as the first mix hop 𝑛 0 of the reply path. Because the adversary operates this mixnode, it can inspect packets arriving at the hop and recognize the reply associated with its own SURB. Operating the mixnode is essential for this attack: inter-node links are protected using Noise (Section 2.1), preventing a passive observer from reading Sphinx headers. The malicious creator, however, already knows the unique header 𝑀0 = (𝛼 0, 𝛽 0, 𝛾 0 ) associated with the SURB and can therefore match 𝛼 0 , 𝛽 0 , or 𝛾 0 against packets observed at the controlled mixnode. A successful match immediately reveals the gateway directly upstream of 𝑛 0 , thereby exposing the replier’s long-term entry gateway. The same attack applies to acknowledgments in the opposite direction. A malicious client acting as the replier constructs a SURB-ACK whose first mix hop is a mixnode under its control. By recognizing the corresponding header when the acknowledgment reaches that mixnode, the adversary identifies the gateway from which it originated and thereby exposes the original SURB creator’s gateway.

Active flooding attack. Gateway discovery also enables Nym’s active flooding attack. An adversary possessing a pool of SURBs can inject a large number of replies toward the victim’s gateway within a short time window, thereby amplifying traffic patterns and facilitating correlation. As documented by Nym, however, this attack requires prior knowledge of the target gateway.5 NymHS does not attempt to prevent flooding itself; instead, it prevents the gateway discovery required to mount the attack against an otherwise anonymous endpoint. Consequences for applications. Any protocol that exchanges unmodified Nym SURBs with potentially untrusted parties (Section 7) inherits these vulnerabilities. Once an endpoint’s gateway is exposed, its anonymity effectively reduces to the security of that single gateway, undermining the protection provided by the mix path. This work therefore addresses two complementary objectives: (i) strengthening SURBs against malicious first- and last-mix-hop attacks while preserving compatibility with Sphinx, and (ii) building a hidden-service protocol for Nym that enables mutually anonymous communication without revealing either endpoint’s gateway.

Malicious last-mix-hop attack. A dual attack combines a malicious replier with a malicious mixnode positioned at the last mix hop before the creator’s gateway, corresponding to the third mix layer in Nym. Because a Nym SURB provides the replier with every mix-derived seed 𝜎𝑖 (Section 2.2), the colluding replier and mixnode can recognize the corresponding reply in two ways. First, from the supplied seeds, the replier derives all 𝑘𝑖𝜋 = ℎ k (𝜎𝑖 ) and can therefore predict the ≈ 2KiB payload ciphertext that will

4

Design Requirements

To construct a hidden-service protocol that securely resists both malicious first- and last-mix-hop attacks, we define the following design requirements. R1 (Replier anonymity). Reply packets transmitted using a SURB must not reveal the replier’s network attachment

4We do not otherwise consider active attacks that are already detectable or mitigated

5 https://nym.com/docs/network/mixnet-mode/anonymous-replies

by mechanisms provided by Nym. 4

...

Proceedings on Privacy Enhancing Technologies YYYY(X)

point, i.e., the replier’s gateway in Nym. In particular, a malicious SURB creator controlling the first mix hop of either the reply path or a SURB-ACK path must not be able to recognize the corresponding packets as they enter the mixnet. R2 (Anonymous service discovery). Clients must be able to discover and contact a hidden service using only its public pseudonym. The discovery protocol must not reveal the association between the service’s pseudonym and its network attachment point to any party, while preserving the anonymity of the client. R3 (Mutual endpoint anonymity). Neither the client nor the hidden service should reveal to any other party the association between its public pseudonym and its network attachment point (e.g., IP address or entry gateway). R4 (Authenticated bidirectional communication). Mutually distrusting parties must be able to authenticate exchanged messages and maintain bidirectional communication using pseudonymous identifiers rather than network identifiers. R5 (Long-lived sessions). Interactive applications require asynchronous bidirectional communication over extended periods without relying on persistent return paths. Unlike circuitbased anonymous networks that reuse fixed paths, NymHS should construct a fresh anonymous route for every transmitted packet while still supporting long-lived sessions. R6 (Sphinx compatibility). The strengthened reply mechanism should preserve the Sphinx packet format and routing semantics. Mixnodes should continue to perform standard Sphinx header processing and probabilistic forwarding without requiring modifications to the underlying routing protocol.

5

inside the final routing block and marking it with the EMBEDDED_KEYS flag. The gateway derives the remaining seed 𝜎 𝜈 −1 = ℎ𝜎 (𝑠 𝜈 −1 ) from its own shared secret. Because 𝐾emb resides inside the onion-encrypted routing block, only the recipient gateway can recover it. Importantly, under this construction, the replier no longer applies the mix-derived payload encryption. It forms 𝑝 = AES ˜ ˜ SURB-ACK∥𝐻 (𝑘)∥Enc (FH∥𝑓 ) with the SURB-ACK and 𝐻 (𝑘) 𝑘˜

left in cleartext outside the AES ciphertext. Upon encountering the EMBEDDED_KEYS flag, the gateway recovers 𝐾emb and uses the embedded seeds, together with its locally derived last-mix-hop seed, to reverse the mix-derived payload transformations. It then AES ˜ forwards the SURB-ACK and delivers 𝐻 (𝑘)∥Enc (FH∥ 𝑓 ) to 𝑘˜ the client, which matches the digest to the corresponding key and decrypts the AES ciphertext. This defense leaves the Sphinx packet format and header size unchanged while eliminating both last-mix-hop payload matching and seed matching.6 The complete equations are provided in Appendix A.4.7

5.2

Methodology

In this section, we first present our defense against the malicious last-mix-hop attack (Section 5.1), followed by replier-anonymous SURBs that prevent first-mix-hop header matching (Section 5.2). We then introduce NymHS, our hidden-service protocol for the Nym mixnet (Section 5.3).

5.1

Withholding Mix-Derived Payload-Key Seeds from the Replier

POTP payload encryption. POTP replaces 𝜋𝑘 (Section 2.2) with XOR against a per-hop pseudorandom stream. With PRGℓ : {0, 1}𝜅 → {0, 1}ℓ ,

Standard Nym SURBs disclose every mix-derived seed 𝜎𝑖 to the replier, allowing it to derive the per-hop payload keys 𝑘𝑖 = ℎ k (𝜎𝑖 ). As shown in Section 3, these keys enable a malicious replier that additionally controls the last mix hop of the reply path to recognize the corresponding packet through payload or shared secret matching. However, the mix-derived seeds need not be disclosed to the replier and can instead be provided directly to the creator’s gateway. Accordingly, the replier receives only the orig˜ inal Sphinx SURB format [5], S★ = (𝑛 0, 𝑀0, 𝑘),instead of Nym’s ˜ extended (𝑛 0, 𝑀0, 𝜎0, . . . , 𝜎 𝜈 −1, 𝑘). In addition, Nym headers support up to 𝑟 = 5 Sphinx hops, whereas ordinary reply paths use only 4 hops, leaving approximately 60 B of unused space in the final-hop routing block 𝛽. The creator exploits this unused capacity by embedding 𝐾emb = 𝜎0 ∥𝜎1 ∥𝜎2,

Extending SURBs with Replier Anonymity

As discussed earlier, standard SURBs do not provide replier anonymity because 𝑀0 enters the mixnet directly from the replier’s gateway. Consequently, a malicious SURB creator that controls the first mixnode on the reply route can recognize the corresponding header and infer the replier’s long-term gateway. To prevent this attack, the replier must avoid injecting the reply directly onto the precomputed SURB route. We therefore conceal 𝑀0 until a designated swap hop by carrying it inside an independently routed outer Sphinx packet. The outer packet first traverses a separate route to the swap node, which then transfers the packet onto the original reply route. As a result, the first mixnode of the inner route observes the packet arriving from the swap node rather than from the replier’s gateway, satisfying Requirements R1 and R6. Carrying the inner header increases the payload size from ℓ to ℓ + |𝑀 |. We additionally replace the Sphinx payload permutation 𝜋 with a length-preserving pseudo one-time pad (POTP), while leaving Sphinx header processing unchanged. The inner SURB is the S★ construction introduced in Section 5.1: the replier holds 𝑘˜ but does not receive the inner mix-derived seeds.8

Enc𝑘POTP (𝑥) = 𝑥 ⊕ PRG |𝑥 | (𝑘),

Dec𝑘POTP (𝑐) = 𝑐 ⊕ PRG |𝑐 | (𝑘), (1)

Enc𝑘POTP (𝑥) = |𝑥 |. To transport the SURB header to the swap hop, the padding procedure reserves an auxiliary suffix 𝑚: PadPOTP (𝑝, 𝑚, ℓ) = 𝑝 ∥0x01∥0ℓ − |𝑝 | − |𝑚 | −1 ∥𝑚, PadPOTP (𝑝, 𝑚, ℓ) = ℓ.

(2)

6 The hybrid games 𝐺 –𝐺 of Danezis and Goldberg [5] continue to apply. 3 7 Section 5.2 uses S★ as the inner SURB of a rewrapped reply. 8 Notation follows Appendix A.1; standard SURB replies are described in Section 2.2.

|𝐾emb | = 3𝜅 = 48 B, 5

Proceedings on Privacy Enhancing Technologies YYYY(X)

Constantinides et al.

˜ with 𝑀0 = Inner reply construction. Let S★ = (𝑛 0, 𝑀0, 𝑘) (𝛼 0, 𝛽 0, 𝛾 0 ) as in Section 5.1. Write 𝑚 0 for the |𝑀 |-byte encoding of 𝑀0 . For fragment 𝑓𝑖 , following Section 2.2, the replier forms AES ˜ 𝑝𝑖 = SURB-ACK𝑖 ∥𝐻 (𝑘)∥Enc (FH𝑖 ∥𝑓𝑖 ),

of the inner route. Table 3 summarizes the resulting differences between standard and replier-anonymous SURBs.

5.3

𝑘˜

˜ remaining in cleartext outside the with the SURB-ACK and 𝐻 (𝑘) AES ciphertext. Unlike the construction in Section 2.2, the replier does not apply the inner mix keys 𝑘 0POTP, . . . , 𝑘 𝜈POTP −1 because the corresponding seeds are embedded in 𝛽 𝜈 −1 as 𝐾emb . Instead, it pads the reply into the extended payload field while embedding the inner header 𝑚 0 : 𝛿 0 = PadPOTP (𝑝𝑖 , 𝑚 0, ℓ+|𝑀 |),

|𝛿 0 | = ℓ+|𝑀 |,

tail |𝑀 | (𝛿 0 ) = 𝑚 0 . (3)

Outer rewrap and header swap. The replier constructs its own ′ fresh Sphinx header 𝑀0′ on a route (𝑛 0′ , . . . , 𝑛𝐷 −1 ) of depth 𝐷 that it selects independently of the inner route, and encapsulates 𝛿 0 in the resulting outer packet (𝑀0′ , 𝛿 0′ ); unlike the inner header 𝑀0 , which the creator precomputed and supplied in the SURB, 𝑀0′ is ′ generated by the replier. The final outer hop 𝑛𝐷 −1 is marked with SWAP_HEADER, and the inner first mix hop 𝑛 0 is embedded in 𝛽𝐷′ −1 (Appendix A.2). Outer seeds/keys satisfy 𝜎 𝑗′ = ℎ𝜎 (𝑠 ′𝑗 ) and 𝑘 POTP′ = ℎ k (𝜎 𝑗′ ): 𝑗   POTP 𝛿 0′ = Enc𝑘POTP (4) POTP′ · · · Enc𝑘 POTP′ (𝛿 0 ) · · · . 0

𝐷 −1

Each outer hop processes the Sphinx header and removes its corre′ sponding POTP layer as usual. At 𝑛𝐷 −1 , the SWAP_HEADER flag instructs the node to recover 𝑛 0 from 𝛽𝐷′ −1 , remove the final outer POTP layer to obtain 𝛿 0 , and split 𝑚 0 = tail |𝑀 | (𝛿 0 ),

(5)

𝛿 body = headℓ (𝛿 0 ),

(6)

The NymHS Hidden-Service Protocol

Building on the replier-anonymous SURBs developed above, we introduce NymHS, a hidden-service protocol for the Nym mixnet that enables mutually anonymous communication between clients and services. NymHS combines authenticated SURB publication, anonymous service discovery, pseudonymous session establishment, asynchronous bidirectional communication, and anonymous SURB replenishment through a rendezvous layer of repository nodes. Specifically, repositories store precomputed SURBs but do not participate in end-to-end communication. Hidden services periodically publish authenticated SURBs to a deterministically selected set of repositories, allowing clients to anonymously retrieve fresh reply paths without revealing the service’s network location. All communication among clients, services, and repositories is carried in Sphinx packets routed through the mixnet. Reply and acknowledgment packets use the replier-anonymous SURBs introduced in Section 5.2, thereby satisfying Requirements R1 and R6. At the application layer, messages carry an Ed25519 senderTag, a message kind, a signature 𝜎, and a fresh nonce to provide authentication, integrity, and replay protection (Table 5). The prototype binaries and kind dispatch mechanism are summarized in Appendix B.

Roles in the Protocol The NymHS protocol involves the following roles: • Client: An entity that initiates communication with a hidden service while concealing its own network location. • Hidden Service: A service that receives and responds to client requests while concealing its network location. • Repository Nodes: A set of nodes responsible for storing and forwarding signed SURBs published by hidden services, as well as encrypted SURBs exchanged by clients and hidden services. All communication among these entities is conducted exclusively through the mixnet.

parsing 𝑚 0 as 𝑀0 . The node then replaces the extracted header $

bytes with fresh randomness 𝑅 ← − {0, 1} |𝑀 | , forming 𝛿 0★ = 𝛿 body ∥𝑅, and forwards (𝑀0, 𝛿 0★) to 𝑛 0 . From this point onward, the packet follows the inner path described in Section 5.1: each mixnode removes its locally derived payload layer, and the gateway recovers 𝐾emb upon processing the EMBEDDED_KEYS flag. Consequently, 𝑛 0 receives 𝑀0 from the swap node rather than directly from the replier’s gateway, defeating the first-mix-hop attack described in Section 3. At the same time, the replier never obtains the inner mix-derived seeds required to perform last-mix-hop matching. The resulting SURB representation is also 64 bytes smaller.

Terminology. Creator and replier name roles on a single SURB and cut across the roles above. Either party can hold either: a client creates the SURBs on which it expects replies, whereas a hidden service creates the SURBs that clients use to reach it. Because a SURB returns to whoever created it, its destination is likewise a client in the first case and a service in the second.

Security of the first-mix-hop defense. POTP preserves the payload length while replacing the Sphinx payload permutation with a pseudorandom one-time pad. Under the security of the underlying PRG, the resulting ciphertext is computationally indistinguishable from a uniformly random string of the same length. Moreover, because 𝑀0 remains concealed until the swap hop emits (𝑀0, 𝛿 0★), a malicious SURB creator controlling 𝑛 0 cannot associate the observed header with the replier’s gateway. Rewrap-and-swap slightly relaxes the stratified routing structure of Nym [6], as the swap node may forward a packet from a later layer of the outer route to the first layer

SURB Publication and Verification Before clients can initiate communication, hidden services publish fresh SURBs to the repository layer. The publication process proceeds as follows: (1) The service computes ℎ(𝑃𝐾𝑆 ∥ epoch), where epoch denotes the current network-wide epoch, i.e., a fixed-duration interval defined by the Nym protocol during which the network topology remains stable before being refreshed [6]. The resulting digest is used to select the 𝑁 closest repository nodes for SURB storage. 6

...

Proceedings on Privacy Enhancing Technologies YYYY(X)

(2) For each selected repository node R𝑖 , the service sends a message through the mixnet containing: (i) the service public key 𝑃𝐾𝑆 ; (ii) a large secret value U shared between the service and R𝑖 ; (iii) a set of signed service SURBs S𝑆 = {(S 𝑗 , sig 𝑗 )}𝑛𝑗=1 ; aux }𝑚 , used (iv) a set of auxiliary service SURBs S𝑆aux = {S𝑆,𝑘 𝑘=1 for acknowledgments and replenishment requests. (3) Upon receiving the publication, R𝑖 verifies the signatures. If verification succeeds, the repository stores the SURBs in a data structure indexed by the service public key 𝑃𝐾𝑆 and returns an acknowledgment using one auxiliary service SURB from S𝑆aux . Otherwise, the publication is discarded and an error is returned. Because repositories index published SURBs by 𝑃𝐾𝑆 , the service public key effectively serves as a stable, location-independent address. Any client that knows 𝑃𝐾𝑆 can derive the same repository set, retrieve fresh reply paths, and contact the service without learning its gateway or underlying network location.

(1) The client initiates communication by transmitting authenticated web requests using the retrieved service SURBs (Section 5) and includes its session public key 𝑝𝑘𝐶sess . The hidden service uses this key to authenticate requests and associate them with the corresponding pseudonymous session. The 𝐶 , initial request carries a larger set of bootstrap SURBs Sboot 𝐶 𝐶 where |Sboot | ≫ |Scont |, to establish sufficient reply capacity. Each subsequent request carries a smaller set of continuation 𝐶 SURBs Scont to replenish the reply paths consumed during the session. (2) The hidden service stores the received SURBs indexed by 𝑝𝑘𝐶sess , forwards authenticated requests to a local application endpoint, and returns signed responses through the stored SURBs using replier-anonymous replies (Section 5.2). Each response additionally carries fresh reply SURBs Sserver , allowing the client to continue communicating without exhausting its available reply paths. (3) Both the client and the service reserve a fixed threshold of SURBs, denoted by 𝜏, exclusively for replenishment. This reserve ensures that control communication remains possible even when the general-purpose SURB pool is nearly exhausted. (4) If either party determines that transmitting a message would reduce its available SURB pool below 𝜏, the message is buffered and a replenishment protocol is initiated through a rendezvous point identified by rid: (i) the requester generates a Diffie–Hellman public key share 𝑔𝑥 and transmits it together with the requested number of SURBs 𝑛 req , referencing the session pseudonym 𝑝𝑘𝐶sess carried in the senderTag field (Table 5); (ii) the peer generates its own Diffie–Hellman share 𝑔 𝑦 , derives the shared secret 𝐾 = 𝑔𝑥 𝑦 , and generates a fresh set of SURBs Snew with |Snew | = 𝑛 req + 𝑐, where 𝑐 is a protocol-defined replenishment reserve. The peer encrypts the SURB set under 𝐾 and forwards the encrypted bundle to a selected repository node together with a rendezvous identifier rid; (iii) after the repository node confirms storage, the peer informs the requester of rid, the selected repository node, and the number of SURBs 𝑛 ret required to retrieve the stored bundle; (iv) The requester generates 𝑛 ret + 𝑐 SURBs, where 𝑐 is a protocol constant accounting for auxiliary communication, and anonymously retrieves the encrypted SURB bundle by presenting rid together with the corresponding SURBs. The repository node returns the encrypted bundle through the supplied SURBs, after which the requester decrypts Snew using 𝐾 and resumes normal communication.

SURB Retrieval by the Client Once a hidden service has published its SURBs, clients can retrieve them anonymously through the repository layer: (1) The client computes ℎ(𝑃𝐾𝑆 ∥ epoch) to identify the same set of 𝑁 repository nodes selected by the service. (2) The client randomly selects one repository node R𝑖 and sends a retrieval request through the mixnet, including the service public key 𝑃𝐾𝑆 and a set of auxiliary client SURBs aux }𝑚 ′ for receiving the response. S𝐶aux = {S𝐶,𝑗 𝑗=1 (3) If at least 𝑘 valid service SURBs are available, R𝑖 returns them to the client using SURBs from S𝐶aux . The client verifies the received SURBs and stores them locally. (4) If fewer than 𝑘 SURBs are available: (i) the repository node returns an error to the client using an auxiliary client SURB; (ii) if the service is already known to the repository, the repository initiates a replenishment request to the service using auxiliary service SURBs from S𝑆aux and the shared secret U; (iii) the client may retry the retrieval after replenishment or contact another repository node from the derived repository set. The client stores the retrieved SURBs in a local data structure indexed by the hidden service public key.

Establishing Communication with the Hidden Service Once the client has obtained a sufficient number of valid SURBs, it can initiate anonymous communication with the hidden service. At the beginning of each session, the client generates an ephemeral key pair (𝑠𝑘𝐶sess, 𝑝𝑘𝐶sess ). The public key 𝑝𝑘𝐶sess serves as a sessionscoped pseudonym in messages sent to the service. It does not reveal the client’s network identity; instead, the service uses it to index session-specific state, including stored SURBs, and to verify incoming packets. Communication proceeds as follows:

Design requirements. The protocol satisfies the design requirements defined in Section 4 as follows. Replier-anonymous SURBs conceal the replier’s gateway while preserving compatibility with the Sphinx packet format and routing semantics, thereby satisfying Requirements R1 and R6. SURB publication and anonymous retrieval through the repository layer enable clients to discover and contact a hidden service using only its NymHS pseudonym, satisfying Requirement R2. Session establishment through ephemeral 7

Proceedings on Privacy Enhancing Technologies YYYY(X)

Constantinides et al. Measurement host (Linux)

pseudonymous identifiers, combined with SURB-based communication, ensures that neither endpoint reveals its network identifier or entry gateway to the other party, satisfying Requirement R3. The authenticated message format together with Ed25519 signatures provides authenticated bidirectional communication, satisfying Requirement R4. Finally, continuous SURB replenishment supports asynchronous communication over extended periods without requiring persistent circuits or fixed return paths, satisfying Requirement R5.

Repeat 1–N

Origin stack (Linux)

Docker container

N Benchmark harness

2 11 Playwright Chromium Repeat 3–10

M

3 10

Web server

1

6

5

7

4 9

8

SU

RB

tio

n/

rep le

nis

nym-sphinx-socks

Hidden service

pu

bli ca

Linux host (mixnodes & gateways)

hm

ent

5.4

Prototype Implementation

Repository node

We implemented NymHS as an extension of the Nym SDK, adding the replier-anonymous SURBs of Section 5.2 and the hidden-service protocol of Section 5.3 across a client proxy, a hidden service, and a repository node. Mixnodes require only the POTP payload format and the additional routing flags of Section 5.2; entry gateways rewrap the acknowledgments they inject, and Loopix scheduling is unchanged from Section 2.1. Appendix B gives the binaries, the Sphinx-layer changes, and the build parameters.

6

Evaluation

1

Local

Description

Figure 1: Evaluation workflow for one page-load observation on a single Linux server (mixnet in Docker; other components native). Steps 1–2 run once per page; 3–10 repeat per HTTP GET; 11 is the browser load event; M/N record metrics and rotate the template. Steps 1–N repeat over the 118 corpus documents (table below). Diagram drawn with AI assistance to the authors’ specification.

Objectives

RQ1. How do payload size ℓ and rewrap depth 𝐷 affect end-to-end page-load latency? RQ2. What fragmentation overhead does NymHS incur per reply fragment, and to what extent does increasing payload size reduce that overhead and improve throughput?

6.2

Scope

POST /metrics/reset on the CP — zero counters and start a new epoch Harness directs Playwright to GET hs_pk.sphinx, the 2 Local HS recipient key 3 Local Browser issues one HTTP GET via CP SOCKS (first: document from page.goto; then each referenced CSS, JS, image, . . . ) 4 Mixnet CP encapsulates one HTTP GET and forwards it through the mixnet Mixnet delivers encrypted request fragments to the HS 5 Mixnet 6 Origin HS reassembles fragments and forwards the HTTP GET to the WS 7 Origin WS returns the HTTP response to the HS 8 Mixnet HS fragments and encrypts the response, returning it on the client’s reply SURBs 9 Mixnet Mixnet delivers encrypted response fragments to the CP 10 Local CP reassembles each response and forwards it to the browser Repeat 3–10 Local + Mixnet As each fetched document is parsed, the browser discovers referenced subresources (e.g., index.html linking an image, a stylesheet, or a script) and issues a separate HTTP GET for each; steps 3–10 repeat for every such GET until the load event 11 Local Playwright load event unblocks and reports completion to the harness M Local GET /metrics after load — record 𝑇load and counters to CSV N Local POST /__bench/next on the WS — deploy next benchmark template 1–N Local Repeat for each corpus document until all 118 templates are visited

In this section, we empirically evaluate NymHS. Before presenting the results, we first describe the evaluation setting and the performance characteristics that motivate our experiments. Nym currently uses a 2 KiB Sphinx payload size, with client data transmitted into the mixnet according to a Poisson process with a mean inter-departure time of 20 ms. This limits the resulting application-data throughput to approximately 100 KiB/s. At this packet size, roughly one fifth of each reply fragment is consumed by fixed metadata and routing information, further reducing the effective payload capacity. Moreover, reported broadband speeds are on the order of several megabytes per second [28], making the mixnet’s real traffic stream— rather than the client’s access link—the primary throughput bottleneck. We therefore evaluate larger payload sizes to determine how amortizing this fixed overhead reduces fragmentation and improves performance. We additionally vary the rewrap depth to quantify the latency cost introduced by replier anonymity. Under this setting, we benchmark a single NymHS hidden service on one host using 118 static websites under a 9 × 3 experimental design with ℓ ∈ {2, 3, . . . , 10} KiB and 𝐷 ∈ {1, 2, 3}. Each of the 27 configurations is evaluated three times across all 118 websites, resulting in 9,558 page loads.

6.1

Step

Mixnet topology. The mixnet comprises two entry gateways, eight mixnodes in three stratified layers and a Network Requester. System components. We deployed four NymHS processes: (1) a Repository Node (RN) that stores authenticated SURBs published by hidden services and coordinates SURB replenishment;

Experimental Testbed

All experiments ran on a single virtual private server hosting the Nym mixnet and the NymHS binaries described in Section 5.3. Figure 1 depicts the measurement workflow for one page-load observation. 8

...

Proceedings on Privacy Enhancing Technologies YYYY(X)

40

Page-load latency, Tload (s)

(2) a Web Server (WS) hosting the benchmark site at /. The harness rotates templates through local POST /__bench/next and GET /__bench/status endpoints; (3) a Hidden Service (HS) that terminates mixnet requests, fetches content from the WS, fragments responses into Sphinx packets, and returns them via client-supplied reply SURBs; (4) a Client Proxy (CP) exposing a SOCKS interface and translating HTTP into hidden-service messages. For benchmarking, the CP exposes POST /metrics/reset and GET /metrics; counters are reset before each page load and read after the browser load event.

25 20 15 10 2

3

4

5

6

7

8

Sphinx payload size (KiB)

9

10

Figure 2: Mean page-load latency 𝑇load versus payload size ℓ for rewrap depths 𝐷 ∈ {1, 2, 3}.

Rationale of the experimental setup. All components ran on a single host to isolate the effects of ℓ and 𝐷 under fixed hardware and software. The evaluation could not use the public Nym network because NymHS changes Sphinx payload encryption (POTP) and sphinx routing (SWAP_HEADER,EMBEDDED_KEYS), which we do not control on public mix nodes or gateways; wide-area variability would also confound latency measurements. We evaluate larger ℓ rather than a shorter Poisson interval because a higher transmission rate alone would increase fragmentation, and each additional fragment would carry the same fixed SURB metadata overhead.

6.3

30

5

Benchmark harness. A separate harness orchestrates experiments without joining the mixnet. For each page it resets CP counters (POST /metrics/reset), drives headless Chromium through Playwright [21] with the CP SOCKS proxy, loads the HS .sphinx URL, waits for the browser load event, records metrics (GET /metrics), and advances the WS template (POST /__bench/next). Each reported epoch covers one end-to-end page retrieval.

D=1 D=2 D=3

35

measurement completes when the browser reaches the load event or after a timeout of 600 s. Experimental Variables. We swept two parameters: • Payload size (ℓ): {2, 3, . . . , 10} KiB. Replier-anonymous replies use payload field size ℓ + |𝑀 | with |𝑀 | = 348 B (Section 5.2). • Rewrap depth (𝐷): {1, 2, 3} mixnodes on the rewrap route before header swap. This yields a 9 × 3 design: twenty-seven configurations, each evaluated on all 118 templates and repeated three times (9,558 page-load measurements). 6.3.2

Experimental Methodology

To assess the impact of ℓ and 𝐷 on NymHS, we vary both parameters in a full-factorial design, rebuilding and restarting the stack for each of the twenty-seven configurations while holding the workload and host environment constant. Our primary outcome is the page-load latency 𝑇load .

6.4

Latency Evaluation

RQ1 asks how payload size ℓ and rewrap depth 𝐷 affect browsing latency. Each reply fragment is a fixed-size packet that leaves the replier’s queue under Loopix’s Poisson schedule (Section 2.1), so smaller ℓ forces more fragments per page. Rewrap depth 𝐷 sends every fragment through 𝐷 outer mix hops (Section 5.2), each peeling a Sphinx layer, removing a POTP layer and drawing a mix delay, but fragment count depends only on ℓ.

6.3.1 Workload. The workload comprises 118 static website templates (HTML with associated CSS, JavaScript, and images) obtained from a publicly available template repository.9 Before benchmarking, all templates are preprocessed offline so that every resource is served locally by the WS. External assets (stylesheets, scripts, fonts, and images) are downloaded and their references rewritten to local copies. Unresolved external resources and references to missing local files are removed to prevent spurious HTTP 404 requests during evaluation. Consequently, every browser request traverses the mixnet. We exclude directories that ship only screenshots of templates and no index.html, since there is no page in them to load. Each template is loaded once per configuration through the hidden service using Playwright and the CP with browser caching disabled, and the full design is repeated three times. The host is a virtual private server whose resources are shared with other tenants, so repetition limits the influence of contention on any one run. A

6.4.1 Results. At 𝐷 = 1, raising ℓ from 2 KiB to 5 KiB cuts mean latency from 36.06 s to 12.21 s, approximately a 3.0× reduction; raising it further to 10 KiB reaches 6.92 s, 5.2× faster than at 2 KiB. Latency falls with every increase in ℓ and rises with every increase in 𝐷, with no exception anywhere in the grid (Figure 2). Increasing 𝐷 from 1 to 3 adds between 0.36 s and 0.60 s. Throughput bound. The Poisson schedule of Section 2.1 has a 20 ms mean interval, so a client sends approximately 50 packets per second whatever the payload size. Each packet carries ℓ − 445 B of application data, where the 445 B of fixed metadata is itemised in Section 6.5, bounding sustained throughput at 50(ℓ − 445) B/s: the App. KiB/s column of Table 1, from 78.3 KiB/s at ℓ = 2 KiB to 478.3 KiB/s at ℓ = 10 KiB. Since the packet rate is fixed, the only way to send more application data is to put more of it in each packet,

9 https://github.com/learning-zone/website-templates.git

9

Proceedings on Privacy Enhancing Technologies YYYY(X)

Constantinides et al.

Table 1: Per-fragment application budget and page-load latency 𝑇load over 118 websites. Avail. is application bytes per fragment after fixed metadata, OH is 100 × 445/ℓ, and App. KiB/s is sustained application throughput at 50 packets/s. Latencies are mean ± standard deviation over 354 loads per configuration (118 templates × 3 repetitions). The spread is across page loads and reflects the size distribution of the corpus rather than measurement error (Appendix C). 𝑇load (s), mean ± sd ℓ

Avail. (B)

OH (%)

App. KiB/s

1,603 2,627 3,651 4,675 5,699 6,723 7,747 8,771 9,795

21.7 14.5 10.9 8.7 7.2 6.2 5.4 4.8 4.3

78.3 128.3 178.3 228.3 278.3 328.3 378.3 428.3 478.3

2 KiB 3 KiB 4 KiB 5 KiB 6 KiB 7 KiB 8 KiB 9 KiB 10 KiB

𝐷 =1

𝐷 =2

𝐷 =3

36.06 ± 21.70 21.03 ± 12.24 15.31 ± 8.61 12.21 ± 6.68 10.40 ± 5.49 9.10 ± 4.71 8.18 ± 4.10 7.40 ± 3.72 6.92 ± 3.35

36.19 ± 21.80 21.30 ± 12.34 15.54 ± 8.64 12.53 ± 6.72 10.77 ± 5.51 9.35 ± 4.70 8.42 ± 4.16 7.56 ± 3.71 7.05 ± 3.45

36.66 ± 21.94 21.53 ± 12.39 15.77 ± 8.70 12.80 ± 6.81 10.94 ± 5.60 9.45 ± 4.77 8.64 ± 4.26 7.81 ± 3.89 7.37 ± 3.48

which is why the 445 B of fixed metadata costs 21.7% of a 2 KiB packet but only 4.3% of a 10 KiB one.

𝑀. The remaining application payload per fragment is therefore ˜ − |FH𝑖 | − |𝑀 | − 1 = ℓ − 445 B. (ℓ + |𝑀 |) − |SURB-ACK| − |𝐻 (𝑘)|

Why load times vary so widely. A page’s latency is set by how many fragments it needs. At ℓ = 2 KiB each fragment carries 1,603 B of application data. Each response is fragmented as its own set (Section 2.2). A page of 𝐵 bytes delivered in a single response therefore needs ⌈𝐵/1,603⌉ fragments, and a multi-response page somewhat more. The smallest page is a single 2,416 B response needing two fragments, and it loads in 2.3 s; the largest needs at least 2,953 and takes 98 s. Raising ℓ to 10 KiB cuts that same page to at least 484 fragments and 16 s. The standard deviations reported in Table 1 are therefore closely related to the number of fragments required to load each page: larger pages require substantially more fragments and consequently exhibit higher mean load times. Appendix C shows that page-load latency increases approximately linearly with fragment count, to the extent that page size alone provides a strong predictor of load time. This relationship is driven by two main components. First, each page load incurs a per-fragment transmission cost, whose total contribution scales with the number of fragments required. Second, it incurs per-page overhead that is largely independent of the amount of application data transferred, most notably the replenishment protocol, during which reply SURBs must first be deposited at a repository node and subsequently retrieved. Raising ℓ from 2 to 10 KiB multiplies the application data per fragment by 6.1 and scales the transmission term with it, but because of other factors like the replenishment protocol, latency falls only 5.2×. For deployment, ℓ = 10 KiB is the fastest setting, and since 𝐷 costs well under a second at any ℓ it can be set by the anonymity wanted before the header swap rather than by speed.

The relative protocol overhead is therefore 445/ℓ; the OH (%) column in Table 1 reports 100 × 445/ℓ, and App. KiB/s is the corresponding sustained application throughput at 50 packets/s. As payload size increases, the fixed overhead is amortized across larger fragments, reducing the relative overhead from 21.7% to 4.3% and raising application throughput from 78.3 to 478.3 KiB/s.

6.5

Limitations. The corpus is drawn from a single public template repository and consists of static pages, so it does not exercise dynamic content. Our evaluation further assumes that packets are delivered without loss. The measured benefits of larger payloads therefore reflect reduced fragmentation under reliable delivery; packet loss could offset these gains by increasing retransmissions and recovery delay. In addition, all experiments were conducted in a controlled single-host environment, so the results do not capture wide-area effects such as inter-country routing, heterogeneous network paths, or Internet congestion. Evaluating NymHS over geographically distributed deployments is therefore necessary to quantify its end-to-end latency under realistic network conditions.

7

Related Work

This section situates NymHS among prior anonymous communication systems. Section 7.1 compares onion-routing and mixnet architectures that offer or omit hidden services; Section 7.2 discusses metadata-private messaging systems that address a different communication model; and Section 7.3 examines applications built on Nym, including Pudding [17], and how the malicious first-lastmix-hop SURB attacks affects their security claims.

Communication Overhead 7.1

RQ2 quantifies the fragmentation and protocol overhead of NymHS reply packets and shows how increasing payload size amortizes that overhead.

Anonymous Routing Systems

Sphinx and nymservers. Sphinx [5] introduced compact layered routing with constant-size packets, per-hop unlinkability, and SURBs for anonymous replies. It also proposes depositing SURBs at a nymserver [19] that holds a public pseudonym and injects inbound messages via stored SURBs without revealing which network identity owns the pseudonym [5, 19]. Nymservers were conceived primarily to send and receive electronic mail under a pseudonym [4]. Sphinx remains the packet format used by

Fragmentation overhead and available application data. Replieranonymous replies (Section 5.2) use a payload field of size ℓ + |𝑀 |, where |𝑀 | = 348 B is the withheld Sphinx header. Of this capacity, every fragment reserves fixed space for protocol metadata ˜ (32 B), the fragment header (Section 2.2): a SURB-ACK (405 B), 𝐻 (𝑘) FH𝑖 (7 B), the one-byte Pad𝑃𝑂𝑇 𝑃 separator, and the embedded header 10

...

Proceedings on Privacy Enhancing Technologies YYYY(X)

Loopix and Nym, but nymservers alone provide neither mutually anonymous client–service rendezvous nor discoverable hidden services.

Stadium. Stadium [31] is a metadata-private messaging system that protects both message contents and communication metadata against a global adversary using differential privacy, cover traffic, and a distributed verifiable mixnet. It assumes that communicating parties already know one another’s identifiers and focuses on concealing the communication relationship between them rather than enabling anonymous service discovery or hidden services. In contrast, NymHS provides mutually anonymous client–server communication through hidden services, allowing clients to discover and communicate with services using only public pseudonyms while hiding the network locations of both endpoints.

Onion routing and Tor. Tor forwards traffic over persistent circuits: fixed relay sequences with FIFO forwarding and layered onion encryption, so each relay learns only its predecessor and successor [29]. A Tor hidden service keeps long-lived circuits, typically refreshed every 18–24 hours, to a small set of relays called introduction points, and publishes those points in a descriptor signed under the service’s long-term public key [3, 23]. A client fetches the descriptor from Hidden Service Directories (HSDirs), builds a circuit to a chosen rendezvous point, and uses an introduction point to ask the service to join that rendezvous over a separate circuit, so neither party reveals its network location. Tor is vulnerable to end-to-end correlation attacks that can deanonymize a connection [6, 14]. Tor provides no built-in Sybil-resistance mechanism, allowing any party to operate relays. This has made adversarial relay operation a realistic threat, with reports of intelligence agencies operating Tor relays for traffic collection and deanonymization attempts [1].

7.3

I2P.. The Invisible Internet Project (I2P) is a peer-to-peer anonymous network in which every participant is both client and relay [11]. Unlike Tor’s bidirectional circuits, I2P uses short-lived unidirectional tunnels and garlic routing [6], and discovers peers through a distributed hash table (DHT) rather than directory authorities [30]. It supports hidden services (eepsites) for intra-network communication [11] but remains vulnerable to censorship, eclipse, and deanonymization attacks [9–12], and—like Tor—targets a local rather than global adversary [6].

Nym service providers. Nym applications communicate through stable Nym addresses. A provider registers identity and encryption keys with an entry gateway, yielding identity.encryption@gateway. A client sends its messages, together with the SURBs it expects answers on, over a route whose last hop is that gateway; the gateway resolves the identity field to the attached party and delivers over a persistent connection. A malicious service provider can leverage the attacks of Section 3: a client that withholds its own address and supplies only SURBs is the creator and the provider the replier, so the attacks expose the client’s gateway, the one attachment point still concealed. Both deployments are repaired without redesign; Figures 8 and 9 in Appendix D show the two configurations. The client supplies S★ in place of a seed-carrying SURB (Section 5.1) and its gateway rewraps the acknowledgment it injects (Section 5.2), so neither the last mix hop of the reply nor the first mix hop of the acknowledgment reveals where the client attaches.

Comparison with Nym. Although Tor and I2P provide hidden services, they target a local adversary and weaken when both communication ends (or a large network fraction) are observed. Nym’s Loopix design instead uses independently routed Sphinx packets, probabilistic delays, and continuous cover traffic against a passive global adversary, with stake-based Sybil resistance [6, 7]. Prior to this work Nym lacked a hidden-service protocol; NymHS fills that gap while preventing the malicious-mix-hop SURB attacks. Table 2 summarizes these differences. The final row reflects Nym prior to this work: NymHS adds hidden-service support while retaining the mixnet properties above.

7.2

Applications Built on the Nym Mixnet

Clearnet browsing via exit gateways. To reach the public Internet a Nym client does not dial the destination itself: its entry gateway injects Sphinx packets toward an exit gateway, which terminates the anonymous path, opens the TCP/TLS session, and answers through client-supplied SURBs. The exit necessarily learns the destination; what the mixnet must keep from it is which entry gateway originated the request, and so the client’s long-term attachment point. Answering on SURBs, however, makes the exit a replier, so both attacks of Section 3 are available to it and both disclose exactly that gateway, reducing deanonymization to compromising or flooding one gateway rather than breaking the full mix path.

Pudding. Pudding [17] provides private user discovery on Loopix/Nym: a client contacts a peer knowing only a short username such as an email address. Users register with discovery servers, proving ownership of that identifier and storing their Nym contact information under it; a querier looks the username up at several servers, which return a matching deterministically generated SURB (Appendix A.3), and sends a first contact message through it via a reflector. Two of its goals concern us: G1 (unlinkability), that lookups of the same target by different honest users be indistinguishable, and G4 (membership unobservability), that outsiders cannot tell whether a username is registered; G2 and G3 cover impersonation resistance and binding to a real-world identifier, which our attack does not touch. Unregistered usernames still yield a SURB, addressed to a sink, so the reply format alone

Anonymous Messaging Systems

Kerblam. Kerblam [13] is a two-server anonymous messaging system that provides end-to-end unlinkability, ensuring that neither the sender nor the receiver learns the other’s identity. It achieves this through oblivious message retrieval, oblivious shuffling, and a specialized ORAM− construction for efficient asynchronous retrieval of large messages. In contrast, NymHS builds on a decentralized Loopix/Nym mixnet rather than two non-colluding servers. While Kerblam focuses on mutually anonymous messaging, NymHS additionally supports hidden services, enabling anonymous client– server communication for web applications in which clients can issue requests and receive responses without revealing either endpoint’s network location. 11

Proceedings on Privacy Enhancing Technologies YYYY(X)

Constantinides et al.

Table 2: Architectural comparison between Tor, I2P, and the Nym mixnet. Property Architecture type Communication model Packet ordering preserved Probabilistic forwarding delays Continuous loop cover traffic End-to-end-correlation resistance Website-fingerprinting resistance Passive global adversary model Sybil-resistance incentives Unrestricted relay participation Hidden-service support

Tor Onion routing Persistent circuits ✓ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓

does not reveal membership. These goals cover discovery rather than long-lived mutually anonymous sessions, and a discovery server holds the reachability information Δ registered under each username, and with it that user’s entry gateway.

Nym Mixnet (Loopix) Independent routing ✗ ✓ ✓ Stronger Stronger ✓ ✓ ✗ ✗

Nym codebase and evaluated it across 118 websites and 9,558 page loads. Our results show that reply fragmentation is the dominant factor governing page-load latency: reducing the payload size from 10 to 2 KiB increases mean page-load latency by 29.1 s. These results demonstrate that, with appropriately sized payloads, mutually anonymous hidden services can be implemented practically over mixnets, paving the way for deployable receiver-private services in Nym and related mixnet architectures.

Security implications for Pudding on Nym. Pudding is aware that a discovery-issued SURB header is recognizable, and routes the first contact packet through a reflector so that the known header enters the mixnet away from the querier. It does not address the SURB-ACK variant of the attack (Section 3). A discovery server placed first on a SURB-ACK path can therefore distinguish two users who look up the same target but attach through different entry gateways, breaking G1, and deanonymizes one outright if that gateway is also compromised. G4 assumes mix, provider and discovery nodes are honest, and holds under that model. Their prototype, however, derives the fake contact information from a real mixnet client and reuses that single address for every unregistered lookup, so it names a real entry gateway rather than the nonexistent sink the paper describes. Once the adversary is allowed a mix node, one that recognizes the deterministically generated header sees that same gateway recur across every non-member query while registered lookups disperse across the gateways their owners use, which separates registered from unregistered identifiers more readily than the published design would allow.

8

I2P Peer-to-peer garlic routing Unidirectional tunnels ✓ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓

Ethical Considerations All experiments were carried out on a private mixnet running in Docker on a single host under our control, using 118 static website templates from a public repository served locally. No human subjects were involved, no personal data was collected, and no traffic was ever sent to, observed on, or injected into the live Nym network. We did not use the attacks to deanonymize the gateway of any real user. We notified the Nym developers, and the defenses of Sections 5.1 and 5.2 are published alongside the attacks so that the mitigations are available as the vulnerabilities become public.

Open Science We release an artifact containing both the prototype and the measurements behind Section 6. The implementation comprises the hidden service, the repository node and the .sphinx SOCKS proxy, the Sphinx-layer changes of Sections 5.1 and 5.2, and the containerised test network on which the measurements were taken. The data comprises the 9,558 page loads of the 9×3 design, one CSV per configuration and repetition, together with three analysis scripts: verify.py recomputes each quantitative claim and prints the value stated in the paper beside the value computed from the data; make_table.py regenerates the body of Table 1; and make_figures.py regenerates Figures 2, 6 and 7. Reproducing the reported numbers requires only Python and the included CSVs: no mixnet, no container runtime and no compilation. Reproducing the measurements requires Rust and a host able to run the test network, on which one sweep of the 27 configurations takes on the order of a day. The artifact is available at https://gi thub.com/nionis/nym. A short video showing the hidden service being reached through a browser is at https://www.youtube.com/ watch?v=EcyajkqzK5k.

Conclusion

Although classical mixnet protocols provide strong sender anonymity, they generally lack mechanisms for simultaneously protecting both sender and receiver privacy. Addressing this gap, we presented the first hidden-service protocol for the Nym mixnet. We first showed that naively using standard Sphinx SURBs to provide receiver anonymity introduces two practical attacks in which either a malicious SURB creator or a malicious replier, while additionally controlling only a single mixnode, can expose the other party’s long-term gateway. We then developed defenses against both the first- and last-mix-hop attacks. Building on these defenses, we introduced NymHS, which provides simultaneous sender and receiver anonymity through authenticated SURB publication, anonymous service discovery, pseudonymous sessions, asynchronous bidirectional communication, and SURB replenishment. NymHS requires only limited changes to the underlying mixnet, namely support for the POTP payload format and three additional routing flags. We implemented NymHS on the 12

...

Proceedings on Privacy Enhancing Technologies YYYY(X)

AI Use

[14] Aaron Johnson, Chris Wacek, Rob Jansen, Micah Sherr, and Paul Syverson. 2013. Users get routed: Traffic correlation on Tor by realistic adversaries. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. 337–348. [15] Dimitris Karakostas, Aggelos Kiayias, and Thomas Zacharias. 2024. Blockchain bribing attacks and the efficacy of counterincentives. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. 1031–1045. [16] Dogan Kesdogan, Jan Egner, and Roland Büschkes. 1998. Stop-and-go-mixes providing probabilistic anonymity in an open system. In International Workshop on Information Hiding. Springer, Springer, Portland, OR, USA, 83–98. [17] Ceren Kocaoğullar, Daniel Hugenroth, Martin Kleppmann, and Alastair R. Beresford. 2024. Pudding: Private User Discovery in Anonymity Networks. In Proceedings of the IEEE Symposium on Security and Privacy (SP). IEEE, San Francisco, CA, USA, 3203–3220. https://arxiv.org/abs/2311.10825 [18] Albert Kwon, David Lu, and Srinivas Devadas. 2020. XRD: scalable messaging system with cryptographic privacy. In Proceedings of the 17th Usenix Conference on Networked Systems Design and Implementation. 759–776. [19] David Mazières and M. Frans Kaashoek. 1998. The Design, Implementation and Operation of an Email Pseudonym Server. In Proceedings of the 5th ACM Conference on Computer and Communications Security (CCS). ACM, 27–36. doi:10 .1145/288090.288098 [20] Lennart Oldenburg, Marc Juarez, Enrique Argones Rúa, and Claudia Diaz. 2024. Mixmatch: Flow matching for mixnet traffic. Proceedings on Privacy Enhancing Technologies (2024). [21] Kailash Pathak. 2024. Web Automation Testing Using Playwright: End-to-end, API, accessibility, and visual testing using Playwright (English Edition). Bpb Publications. [22] Ania M Piotrowska, Jamie Hayes, Tariq Elahi, Sebastian Meiser, and George Danezis. 2017. The loopix anonymity system. In 26th USENIX Security Symposium (USENIX Security 17). USENIX Association, Vancouver, BC, Canada, 1199–1216. [23] Florian Platzer, Marcel Schäfer, and Martin Steinebach. 2020. Critical traffic analysis on the tor network. In Proceedings of the 15th International Conference on Availability, Reliability and Security. 1–10. [24] Mahdi Rahimi. 2025. PARSAN-Mix: Packet-Aware Routing and Shuffling with Additional Noise for Latency Optimization in Mix Networks. In International Conference on Applied Cryptography and Network Security. Springer, 159–188. [25] Mahdi Rahimi. 2026. OptiMix: Scalable and Distributed Approaches for Latency Optimization in Modern Mixnets. In The Network and Distributed System Security Symposium. Internet Society. [26] Mahdi Rahimi, Piyush Kumar Sharma, and Claudia Diaz. 2024. LARMix: LatencyAware Routing in Mix Networks. In The Network and Distributed System Security Symposium. Internet Society. [27] Mahdi Rahimi, Piyush Kumar Sharma, and Claudia Diaz. 2025. LAMP: Lightweight Approaches for Latency Minimization in Mixnets with Practical Deployment Considerations. In The Network and Distributed System Security Symposium. Internet Society. [28] Shahriar Shirvani Moghaddam. 2024. The past, present, and future of the internet: A statistical, technical, and functional comparison of wired/wireless fixed/mobile internet. Electronics 13, 10 (2024), 1986. [29] Paul Syverson, Roger Dingledine, and Nick Mathewson. 2004. Tor: The secondgeneration onion router. In Usenix Security, Vol. 10. USENIX Association Berkeley, CA. [30] Carmela Troncoso, Marios Isaakidis, George Danezis, and Harry Halpin. 2017. Systematizing decentralization and privacy: Lessons from 15 years of research and deployments. arXiv preprint arXiv:1704.08065 (2017). [31] Nirvan Tyagi, Yossi Gilad, Derek Leung, Matei Zaharia, and Nickolai Zeldovich. 2017. Stadium: A distributed metadata-private messaging system. In Proceedings of the 26th Symposium on Operating Systems Principles. 423–440. [32] Jelle Van Den Hooff, David Lazar, Matei Zaharia, and Nickolai Zeldovich. 2015. Vuvuzela: Scalable private messaging resistant to traffic analysis. In Proceedings of the 25th Symposium on Operating Systems Principles. 137–152. [33] Bassam Zantout, Ramzi Haraty, et al. 2011. I2P data communication system. In Proceedings of ICN. Citeseer, 401–409.

AI-based tools were used in the preparation of this work, as described below. Writing. The authors used generative AI-based tools (ChatGPT, Claude, and Cursor) to revise the text, improve flow, and correct typos, grammatical errors, and awkward phrasing. Prototype implementation. The prototypes were initially written for a master’s thesis. No AI-based tool generated code at that stage; ChatGPT’s search was used only to locate library documentation and to confirm Rust syntax. Cursor and Claude were then used to rewrite the implementation in full, from the beginning, to make it cleaner and better structured. The authors debugged the resulting implementation manually and verified its correctness, checking every part of the prototype by hand. Data analysis. Cursor and Claude were used to assist with the analysis of the experimental data, and Cursor was used to assist in building the analysis pipeline. Figures. Figures 3 and 4 were drawn with the assistance of Cursor. Figures 5, 8, 9, and 1 were drawn with the assistance of Cursor and Claude. For each figure the authors specified the content, structure, and every element to be depicted, and verified the rendered result; the tools were used to realise those specifications. We have manually verified and are responsible for the accuracy, originality, and integrity of the output of all AI-based tools.

References [1] Emin Çalışkan, Tomáš Minárik, and Anna-Maria Osula. 2015. Technical and legal overview of the tor anonymity network. NATO Cooperative Cyber Defence Centre of Excellence. Available: https://ccdcoe. org/sites/default/files/multimedia/pdf/TOR_Anonymity_Network. pdf (January 4, 2016) (2015). [2] David L Chaum. 1981. Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM 24, 2 (1981), 84–90. [3] Nicolas Constantinides. 2026. I’ve Seen This IP: A Practical Intersection Attack Against Tor Introduction Circuits and Hidden Services. arXiv e-prints (2026), arXiv–2602. [4] George Danezis, Roger Dingledine, and Nick Mathewson. 2003. Mixminion: Design of a type III anonymous remailer protocol. In 2003 Symposium on Security and Privacy, 2003. IEEE, 2–15. [5] George Danezis and Ian Goldberg. 2009. Sphinx: A Compact and Provably Secure Mix Format. In Proceedings of the 30th IEEE Symposium on Security and Privacy (SP 2009). IEEE, Oakland, CA, USA, 269–282. doi:10.1109/SP.2009.15 [6] Claudia Diaz, Harry Halpin, and Aggelos Kiayias. 2021. The Nym Network: The Next Generation of Privacy Infrastructure. White Paper. https://nym.com/nymwhitepaper.pdf Version 1.0, February 26, 2021. [7] Claudia Diaz, Harry Halpin, and Aggelos Kiayias. 2022. Reward sharing for mixnets. (2022). [8] Claudia Diaz and Bart Preneel. 2004. Taxonomy of mixes and dummy traffic. In Information Security Management, Education and Privacy: IFIP 18th World Computer Congress TC11 19th International Information Security Workshops 22–27 August 2004 Toulouse, France. Springer, Springer, Boston, MA, USA, 217–232. [9] Christoph Egger, Johannes Schlumberger, Christopher Kruegel, and Giovanni Vigna. 2013. Practical attacks against the I2P network. In International workshop on recent advances in intrusion detection. Springer, 432–451. [10] Michael Herrmann and Christian Grothoff. 2011. Privacy-implications of performance-based peer selection by onion-routers: a real-world case study using I2P. In International Symposium on Privacy Enhancing Technologies Symposium. Springer, 155–174. [11] Nguyen Phong Hoang, Panagiotis Kintis, Manos Antonakakis, and Michalis Polychronakis. 2018. An empirical study of the i2p anonymity network and its censorship resistance. In Proceedings of the internet measurement conference 2018. 379–392. [12] Seong Hoon Jeong, Ah Reum Kang, Joongheon Kim, Huy Kang Kim, and Aziz Mohaisen. 2016. A Longitudinal Analysis of. i2p Leakage in the Public DNS Infrastructure.. In SIGCOMM, Vol. 16. 557–558. [13] Yanxue Jia, Debajyoti Das, Wenhao Zhang, and Aniket Kate. 2025. Kerblam—Anonymous messaging system protecting both senders and recipients. Cryptology ePrint Archive (2025).

A

Sphinx and SURB Construction Details

This appendix specifies the Sphinx packet construction used in Nym. Section 2.2 covers SURB replies and acknowledgments in the main text; here we give notation, header generation, and the last-mix-hop key-withholding construction (Appendix A.4) needed for the attacks and defenses.

13

Proceedings on Privacy Enhancing Technologies YYYY(X)

A.1

Constantinides et al. 𝜂

Notation and Packet Format

We adopt some of the notation of Danezis and Goldberg [5]. Let 𝜅 denote the security parameter and let 𝐺 be a prime-order cyclic group of order 𝑞 with generator 𝑔, where the Decisional Diffie–Hellman assumption holds. We write 𝐺 ∗ for the non-identity elements of 𝐺. Each mix node 𝑛𝑖 ∈ N has private key 𝑥𝑛𝑖 ∈ Z𝑞∗ and public key 𝑦𝑛𝑖 = 𝑔𝑥𝑛𝑖 , with |𝑦𝑛𝑖 | = 2𝜅. A next-hop routing address 𝑛𝑖+1 encodes network-layer forwarding information (address, port, padding) and is distinct from 𝑦𝑛𝑖+1 ; we assume |𝑛𝑖+1 | = 2𝜅. A destination identifier Δ satisfies |Δ| = 2𝜅. Let 𝑟 be the maximum route length and 𝜈 ≤ 𝑟 the actual length of ordered route (𝑛 0, . . . , 𝑛 𝜈 −1 ). The construction uses key-derivation functions ℎ 𝜇 , ℎ 𝜌 , ℎ𝜎 : 𝐺 ∗ → {0, 1}𝜅 , payload-key hash ℎ k : {0, 1}𝜅 → {0, 1}∗ , replay hash ℎ𝜏 : 𝐺 ∗ → {0, 1}2𝜅 , and blinding function ℎ𝑏 : 𝐺 ∗ × 𝐺 ∗ → Z𝑞∗ . Sphinx employs MAC 𝜇 for integrity, stream cipher 𝜌 for routing-block masking, and keyed permutation family 𝜋 for layered payload encryption. We treat 𝜌 as a keyed pseudorandom generator 𝜌 : {0, 1}𝜅 → {0, 1} (𝑟 +1)𝜂 . For hop 𝑖 with shared secret 𝑠𝑖 ∈ 𝐺 ∗ , define stream 𝜌𝑖 = 𝜌 (ℎ 𝜌 (𝑠𝑖 )); the payload-key seed is 𝜎𝑖 = ℎ𝜎 (𝑠𝑖 ) and the payload key is 𝑘𝑖𝜋 = ℎ k (𝜎𝑖 ) (Section A.2). With Nym’s parameters (𝜅 = 128 bits, 𝑟 = 5), the on-wire Sphinx header size is |𝑀 | = 348 bytes. The payload permutation is

𝜌0

𝜙1 0 𝜌1

𝜙2

Figure 3: Recursive construction of Sphinx filler strings 𝜙𝑖 for 𝜈 = 4 and 𝑟 = 5. Here 𝜌𝑖 denotes the final (𝑖+1)𝜂 bits of 𝜌 (ℎ 𝜌 (𝑠𝑖 )). Filler strings pad routing blocks to fixed length 𝑟𝜂 regardless of actual route length 𝜈. Diagram drawn with AI assistance to the authors’ specification. Filler strings. Starting from 𝜙 0 = 𝜖, the sender computes

Routing blocks. Following Loopix [22], for each forward hop the sender samples delay 𝑑𝑖 ∼ Exp(𝜇) with E[𝑑𝑖 ] = 𝜇, sets 𝑚𝑖 = 𝑓𝑖 ∥𝑣𝑖 ∥𝑑𝑖 , and on the final hop uses 𝑚¯ = 𝑓𝜈 −1 ∥𝑣 𝜈 −1 . Routing blocks 𝑀𝜈 −1, . . . , 𝑀0 are built recursively. The final block is $

𝑥

𝑗 =0 𝑏 𝑗

,

(8) (9)

𝜎𝑖 = ℎ𝜎 (𝑠𝑖 ) ∈ {0, 1}𝜅 ,

(10)

𝑘𝑖𝜋 = ℎ k (𝜎𝑖 ),

(11)

𝑖 = 0, . . . , 𝜈 − 1,

where ℎ𝜎 hashes the shared secret to a seed and ℎ k hashes the seed to a payload key. For plaintext 𝑃, the sender forms 𝑃 ′ = Pad𝜋 (𝑃, ℓ) and computes 𝛿 0 = 𝜋𝑘0𝜋 ◦ · · · ◦ 𝜋𝑘 𝜈𝜋−1 (𝑃 ′ ).

𝑏 0 = ℎ𝑏 (𝛼 0, 𝑠 0 ).

Î𝑖 −1

𝑠𝑖 = 𝑦𝑛𝑖

with |𝑅 𝜈 −1 | chosen so that |𝛽 𝜈 −1 | = 𝑟𝜂. For 0 ≤ 𝑖 < 𝜈 − 1,   𝛽𝑖 = 𝑚𝑖 ∥𝑛𝑖+1 ∥𝛾𝑖+1 ∥ head (𝑟 −1)𝜂 (𝛽𝑖+1 ) ⊕ head𝑟𝜂 (𝜌𝑖 ),

Payload encryption. Payload keys are derived from the per-hop Diffie–Hellman secrets by

For each 𝑖 > 0, ,

(7)

𝛾𝑖 = 𝜇 (ℎ 𝜇 (𝑠𝑖 ), 𝛽𝑖 ).

$

𝑗 =0 𝑏 𝑗

𝑅 𝜈 −1 ← − {0, 1} (𝑟 −𝜈+1)𝜂−𝑐 𝑓 −3𝜅 ,   ¯ 𝛽 𝜈 −1 = (𝑚∥Δ∥𝐼 ∥𝑅 𝜈 −1 ) ⊕ head (𝑟 −𝜈+1)𝜂 (𝜌 𝜈 −1 ) ∥𝜙 𝜈 −1,

The resulting header is 𝑀0 = (𝛼 0, 𝛽 0, 𝛾 0 ).

To construct a header, the sender takes destination Δ, packet identifier 𝐼 , and ordered route with public keys ((𝑛 0, 𝑦𝑛0 ), . . . , (𝑛 𝜈 −1, 𝑦𝑛 𝜈 −1 )).

Î𝑖 −1

0 < 𝑖 < 𝜈.

Figure 3 illustrates this recursion; shaded regions in Figure 4 mark portions of 𝜌 (ℎ 𝜌 (𝑠𝑖 )) not consumed by XOR masking.

.

Header and Routing-Block Construction

𝛼𝑖 = 𝑔𝑥

XOR

𝜙3

Let Alg = (Enc, Dec) denote a symmetric encryption scheme; we Alg Alg write Enc𝑘 and Dec𝑘 for encryption and decryption under key 𝑘. Per-hop forward metadata is 𝑚𝑖 = 𝑓𝑖 ∥𝑣𝑖 ∥𝑑𝑖 with |𝑚𝑖 | = 𝑐; on ¯ = 𝑐 𝑓 < 𝑐. the final hop, 𝑑𝑖 is omitted and 𝑚¯ = 𝑓𝜈 −1 ∥𝑣 𝜈 −1 with |𝑚| The routing flag 𝑓𝑖 distinguishes hop kinds, including FORWARD, FINAL, SWAP_HEADER (Section 5.2), and EMBEDDED_KEYS (Appendix A.4). The routing-block step size is 𝜂 := 3𝜅 + 𝑐. We write head𝑖 (𝑥) and tail𝑖 (𝑥) for prefix and suffix of length 𝑖, ∥ for concatenation, 𝜖 for the empty string, and |𝑥 | for bit-string length. A Sphinx header at hop 𝑖 is 𝑀𝑖 = (𝛼𝑖 , 𝛽𝑖 , 𝛾𝑖 ), where 𝛼𝑖 ∈ 𝐺 is an ephemeral Diffie–Hellman element, 𝛽𝑖 is an encrypted routing block, and 𝛾𝑖 is an integrity tag over 𝛽𝑖 . A complete Sphinx packet is (𝑀0, 𝛿 0 ), where 𝛿 0 is the outermost payload ciphertext.

It samples 𝑥 ← − Z𝑞∗ and sets 𝛼 0 = 𝑔𝑥 , 𝑠 0 = 𝑦𝑛𝑥 0 ,

0

𝜌2

𝜙𝑖 = (𝜙𝑖 −1 ∥0𝜂 ) ⊕ tail𝑖𝜂 (𝜌𝑖 −1 ),

Pad𝜋 (𝑃, ℓ) = 𝑃 ∥0x01∥0

XOR

𝜙2

with Sphinx padding10 ℓ − |𝑃 | −1

XOR

𝜙1

𝜋 : {0, 1}𝜅 × {0, 1}ℓ → {0, 1}ℓ ,

A.2

0

6𝜂

𝑏𝑖 = ℎ𝑏 (𝛼𝑖 , 𝑠𝑖 ).

The packet (𝑀0, 𝛿 0 ) is transmitted to the first mix hop 𝑛 0 . Each mix node removes one layer using the key 𝑘𝑖𝜋 re-derived locally from 𝑠𝑖 (Section 2.2). When a SURB is shipped to a replier, the seeds 𝜎0, . . . , 𝜎 𝜈 −1 are transmitted rather than the derived keys; the replier applies (11) before encrypting (Section 2.2).

10 Classic Sphinx prefixes a 𝜅 -bit zero string before 𝑃 , so Nym’s wire format still

budgets 𝜅+1 bytes (17 B for 𝜅=128 bits) of payload framing beyond the application plaintext. We omit that prefix here; our PadPOTP construction (Section 5.2) likewise uses only the 0x01 separator, optionally followed by an embedded-header suffix.

14

...

Proceedings on Privacy Enhancing Technologies YYYY(X) 2𝜂 Δ 𝐼 𝑚¯

Table 3: Comparison of standard and replier-anonymous SURBs.

4𝜂

𝑅

XOR 𝜌3 3𝜂

Aspect

Standard SURB

Replier-anonymous SURB

Concatenate

Payload encryption SURB contents

Layered pseudorandom permutation Mix-derived payload-key seeds provided to the replier

Pseudo one-time pad

𝛽3

𝜙3

MAC 𝑠3

𝜂

𝜂 𝛽3

𝑚2 𝑛3 𝛾3 XOR

First-mix-hop recognizability First mix hop observes the gateway that injected the reply

𝜌3 𝛽2 MAC

Reply key only; mix-derived seeds recovered at the creator’s gateway First mix hop observes the swap node forwarding the reply header

𝑠2

follows the POTP reply format of Section 5.2 (Eqs. (1)–(2)). Nym uses 𝑟 = 5 routing blocks while ordinary reply paths contain 𝜈 = 4 Sphinx hops (three mix nodes and the recipient gateway), leaving one unused routing step of size 𝜂 in the final routing block.

𝛽2

𝑚1 𝑛2 𝛾2 XOR 𝜌2 𝛽1 MAC

Modified Sphinx construction. Only the final routing block differs from the construction of Section A.2. The SURB creator derives the shared secrets 𝑠𝑖 and payload seeds 𝜎𝑖 = ℎ𝜎 (𝑠𝑖 ) as in Eqs. (10)–(11), and forms 𝐾emb = 𝜎0 ∥𝜎1 ∥ · · · ∥𝜎 𝜈 −2, where |𝐾emb | = (𝜈 − 1)𝜅 (48 B for 𝜈 = 4). The value 𝐾emb replaces part of the random filler in the unused capacity of the final routing block, and the final-hop routing flag is set to EMBEDDED_KEYS:

𝑠1 𝛽1

𝑚0 𝑛1 𝛾1 XOR 𝜌1 𝛽0 MAC 𝑠0 𝛾0

Figure 4: Recursive construction of Sphinx routing blocks for 𝜈 = 4, 𝑟 = 5, and |Δ| = 2𝜅. Each row shows the XOR masking of routing metadata with head(𝜌𝑖 ); integrity tags 𝛾𝑖 authenticate the resulting 𝛽𝑖 . Diagram drawn with AI assistance to the authors’ specification.

𝑚¯ = 𝑓𝜈 −1 ∥𝑣 𝜈 −1,

𝑓𝜈 −1 = EMBEDDED_KEYS,

$

𝑅 𝜈′ −1 ← − {0, 1} (𝑟 −𝜈+1)𝜂−𝑐 𝑓 −3𝜅 − |𝐾emb | ,   ¯ 𝛽 𝜈 −1 = (𝑚∥Δ∥𝐼 ∥𝐾emb ∥𝑅 𝜈′ −1 ) ⊕ head (𝑟 −𝜈+1)𝜂 (𝜌 𝜈 −1 ) ∥𝜙 𝜈 −1, (12)

A.3 Pudding Deterministic SURB Generation

where |𝑅 𝜈′ −1 | is chosen so that |𝛽 𝜈 −1 | = 𝑟𝜂. All preceding routing blocks are constructed exactly as in Section A.2, using the FORWARD flag, yielding the header 𝑀0 = (𝛼 0, 𝛽 0, 𝛾 0 ). Since 𝐾emb appears only inside the onion-encrypted final routing block, a SURB holder that does not know the shared secrets 𝑠 0, . . . , 𝑠 𝜈 −1 cannot recover the embedded payload seeds. Figure 5 illustrates the modification by replacing the final random filler 𝑅 of Figure 4 with 𝐾emb ∥𝑅 ′ .

Pudding [17] adapts the SURB construction of Section 2.2 by replacing every source of randomness with a pseudorandom generator seeded from KDF(nonce ∥ ID ∥ 𝑘). The queried identifier ID, the nonce nonce carried in the lookup message, and a long-lived secret 𝑘 provisioned among the discovery nodes are the only entropy inputs; KDF denotes a key derivation function. The mixnet route (𝑛 0, . . . , 𝑛 𝜈 −1 ) is derived from the same KDF output rather than sampled independently. Given destination reachability information Δ, the modified procedure therefore takes (ID, nonce, Δ) as input and yields a standard SURB whose header, payload keys, and route are fixed by the seed. All honest discovery nodes generate the same SURB for the same triple, keeping responses consistent across replicas. Users do not know 𝑘 and cannot execute this procedure locally; a malicious querier thus cannot precompute the reachability SURB returned for a registered identifier and infer membership from the reply path alone.

SURB creation. Per-hop POTP keys are derived as in (11): 𝑘𝑖POTP = ℎ k (𝜎𝑖 ),

𝑖 = 0, . . . , 𝜈 − 1.

Each mix node derives 𝜎𝑖 = ℎ𝜎 (𝑠𝑖 ) locally from its shared secret, and the gateway similarly derives 𝜎 𝜈 −1 = ℎ𝜎 (𝑠 𝜈 −1 ); hence only 𝜎0, . . . , 𝜎 𝜈 −2 must be embedded in 𝐾emb . The creator samples a $ fresh reply key 𝑘˜ ← − {0, 1}𝜅 and, instead of sending Nym’s seedaugmented SURB
S = 𝑛 0, 𝑀0, 𝜎0, . . . , 𝜎 𝜈 −1, 𝑘˜ ,

A.4 Last-Hop Key Withholding via the Final Routing Block

sends only
S★ = 𝑛 0, 𝑀0, 𝑘˜ , where 𝑀0 contains the embedded seeds in its modified final routing block. Thus the replier never receives the mix-derived seeds directly.

This appendix gives the modified Sphinx header construction used by the last-mix-hop defense of Section 5.1. The payload construction 15

Proceedings on Privacy Enhancing Technologies YYYY(X)

Constantinides et al.

2𝜂 Δ 𝐼 𝑚¯ 𝐾emb

𝑅′

the final hop 𝑛 𝜈 −1 (the recipient gateway), Sphinx processing recovers 𝑚¯ with 𝑓𝜈 −1 = EMBEDDED_KEYS, together with Δ, 𝐼 , and 𝐾emb = 𝜎0 ∥ · · · ∥𝜎 𝜈 −2 . The gateway derives 𝜎 𝜈 −1 = ℎ𝜎 (𝑠 𝜈 −1 ) (hence 𝑘 𝜈POTP −1 = ℎ k (𝜎 𝜈 −1 )) from its own shared secret, derives keys from the embedded seeds by (11),

4𝜂

XOR 𝜌3 3𝜂 𝜙3 Concatenate

𝑘𝑖POTP = ℎ k (𝜎𝑖 ),

𝛽3

MAC 𝑠3

𝜂

𝜂 𝛽3

𝑚2 𝑛3 𝛾3

𝑖 = 0, . . . , 𝜈 − 2,

and peels its own POTP layer to obtain 𝛿 𝜈 −1 . Because EncPOTP = DecPOTP , it restores the padded plaintext except for the 𝑘˜ body layer by POTP Dec𝑘POTP POTP ◦ · · · ◦ Dec𝑘 POTP (𝛿 𝜈 ),

XOR 𝜌3

0

𝛽2

𝜈 −1

forwards the clear SURB-ACK into the mixnet, and delivers AES ˜ 𝐻 (𝑘)∥Enc (FH∥𝑓 ) to the client—including when the client is

MAC

𝑘˜

𝑠2

offline and the gateway must buffer the fragment. The client ˜ it matches 𝐻 (𝑘), ˜ and decrypts EncAES (FH∥ 𝑓 ). Thus alone holds 𝑘: 𝑘˜ gateway-issued acknowledgments are preserved without giving ˜ while the replier never holds the mix-derived POTP the gateway 𝑘, keys required for the last-mix-hop attack of Section 3.

𝛽2

𝑚1 𝑛2 𝛾2 XOR 𝜌2 𝛽1 MAC 𝑠1

B

𝛽1

𝑚0 𝑛1 𝛾1 XOR

Implementation Details

This appendix describes some implementation details of Section 5.2 and the protocol of Section 5.3.

𝜌1 𝛽0 MAC

Binaries. The prototype comprises three mixnet-connected binaries: • Client proxy (nym-sphinx-socks): SOCKS5 termination, SURB retrieval, session state, and replier-anonymous sends. • Hidden service (hidden-service): SURB publication, mixnet session termination, and proxying to a local origin server. • Repository node (repository-server): signature verification, SURB inventory, and rendezvous blob storage.

𝑠0 𝛾0

Figure 5: Recursive construction of Sphinx routing blocks with embedded prior-hop key seeds. Relative to Figure 4, the final-hop filler 𝑅 is replaced by 𝐾emb ∥𝑅 ′ with 𝐾emb = 𝜎0 ∥𝜎1 ∥𝜎2 and 𝑓𝜈 −1 = EMBEDDED_KEYS. Diagram drawn with AI assistance to the authors’ specification.

Sphinx-layer changes. We replace the payload permutation 𝜋 with the length-preserving POTP of Section 5.2, implemented as AES-128-CTR. The per-hop routing flag 𝑓𝑖 then takes one of the values in Table 4, three of which NymHS introduces. A high bit (0x80) on any flag requests per-hop tracing, which we added for debugging and to confirm that replier-anonymous SURBs route as intended. An S★ SURB carries the header and first-hop address alone. With 𝜅 = 16 B and 𝑟 = 5 the header is |𝑀 | = 348 B, so at 𝜈 = 4 a replier receives 396 B where the seed-carrying SURB deployed by Nym gives 460 B. The 64 B difference is the mix-derived seeds whose disclosure to the replier enables the last mix-hop attack of Section 3. They travel in the final-hop padding instead: a 𝜈 = 4 route leaves 68 B of padding, of which 𝐾emb occupies 49 B as a one-byte count followed by 𝜎0 ∥𝜎1 ∥𝜎2 .

Reply encryption. For a reply fragment, AES ˜ 𝑝 = SURB-ACK∥𝐻 (𝑘)∥Enc (FH∥𝑓 ), 𝑘˜

˜ remain outside the 𝑘˜ AES encrypted The SURB-ACK and 𝐻 (𝑘) layer so that the gateway can recover and forward the ACK, and the client can match 𝑘˜ by digest, without learning 𝑘˜ at the gateway. The replier does not apply the mix-derived layers POTP Enc𝑘POTP POTP ◦ · · · ◦ Enc𝑘 POTP , 𝜈 −1

0

and sends (𝑀0, 𝛿 0 ) to 𝑛 0 . Because the replier never learns 𝜎0, . . . , 𝜎 𝜈 −1 , it cannot derive the mix-derived POTP keys or predict the payload ciphertext observed at the last mix hop, preventing last-mix-hop payload matching. Mix and gateway processing. Hops 𝑛 0, . . . , 𝑛 𝜈 −2 process the header as in Section 2.2 and peel one POTP layer with 𝑘𝑖POTP = ℎ k (ℎ𝜎 (𝑠𝑖 )):

Protocol realization. Table 6 lists the hidden-service messages the prototype dispatches, one per value of the kind field of Table 5. The shared secret U of Section 5.3 is a fresh 128-bit value drawn per repository at each publication and carried only in the service’s own upload; a repository serving SURBs to a client omits it. The repository stores U and SENDS it back when asking the service to republish, and the service republishes only on a match. An envelope signature alone therefore does not suffice to trigger a republication.

𝛿𝑖+1 = Dec𝑘POTP POTP (𝛿𝑖 ). 𝑖

(The mix peels act on a payload that was not pre-wrapped under those keys by the replier; as in Danezis and Goldberg [5], the destination undoes this mismatch using the recovered keys.) At

16

...

Proceedings on Privacy Enhancing Technologies YYYY(X)

Table 4: Per-hop routing flags. The last three are introduced by NymHS. Value

Effect at the node

FORWARD FINAL SWAP_HEADER

1 2 3

EMBEDDED_KEYS

4

ACK_FINAL

6

Peel one layer, delay, forward. Recover Δ and the payload. Extract 𝑀0 from the payload tail, replace it with fresh randomness, forward under 𝑀0 . Parsed as FINAL, then recover 𝐾emb and undo the mix-key mismatch. Parsed as FINAL, but only the leading AckPacket payload bytes are the acknowledgment.

Page-load latency, Tload (s)

Flag

100

kind

𝜎

nonce

C

Publish or return signed service HS → RN; SURBs keyed by 𝑃𝐾𝑆 . RN → CP Ask RN for 𝑘 fresh signed SURBs CP → RN for 𝑃𝐾𝑆 . Report publish/retrieve outcome. RN → HS/CP Ask HS to republish when RN → HS inventory < 𝑘 . Store encrypted replenishment HS/CP → RN SURB bundle. Confirm blob stored under rid. RN → peer Fetch stored blob by rid/nonce. CP/HS → RN Return stored ciphertext to RN → req. requester. Start peer replenishment (DH + req. → peer quota). Point requester to blob and reply peer → req. budget. Authenticated application request. CP → HS Signed application response on HS → CP reply SURBs.

SURBRequest PublicationStatus SURBReplenish Request StoreRendezvous Blob PublicationAck RendezvousLookup RendezvousBlob Rendezvous Establish RendezvousPointer ApplicationRequest Application Response

20

500

1000

1500

2000

2500

Fragments required by the page

3000

Latency and Fragment Count

Section 6.4 attributes page-load latency to the number of Sphinx fragments a page requires. We estimate that count by dividing the returned bytes by the ℓ −445 bytes of application data each fragment carries (Section 6.5). The estimate is a lower bound: resources are fragmented independently, so spreading the same bytes across more resources can require additional fragments. Latency is approximately linear in the estimated count at every payload size (Figure 6). Least-squares fits give per-fragment slopes of 30.6, 27.5, and 28.2 ms at ℓ = 2, 5, and 10 KiB, so a page of 𝐹 fragments loads in approximately 7.9 + 0.031𝐹 seconds at ℓ = 2 KiB and 2.7 + 0.028𝐹 seconds at ℓ = 10 KiB. At ℓ = 2 KiB the residual standard deviation is 4.3 s, against 21.7 s when load time is predicted from the corpus mean alone. The residual is structural rather than noise: averaging each template over its three runs (Figure 7) reduces the residual standard deviations only from 4.3, 1.5, and 1.0 s to 3.9, 1.3, and 0.9 s at ℓ = 2, 5, and 10 KiB. What the estimate does not capture—per-response fragmentation granularity, and rendezvous replenishment rounds that install SURBs in fixed blocks at the cost of a mixnet round trip independent of page size—accounts for most of it.

From → To

SignedSURBBundle

40

Figure 6: Page-load latency versus estimated fragment count at 𝐷 = 1. Each point represents one measured load for each of the 118 templates across three runs; lines show least-squares fits.

Table 6: Prototype dispatch of kind values (paper names). CP = client proxy, HS = hidden service, RN = repository node. Purpose

60

0

Description Ed25519 public key serving as a pseudonymous sender identifier. Message type: publication, retrieval, replenishment, session, or application data. Ed25519 signature providing message authenticity and integrity. Fresh nonce used to prevent replay attacks.

Message

80

0

Table 5: Authenticated hidden-service message format. Field senderTag

= 2 KiB = 5 KiB = 10 KiB

D Use Cases for Replier-Anonymous SURBs D.1 Clearnet Browsing As Section 7.3 notes, the exit gateway is the replier: the network requester it runs embedded answers on the client’s SURBs, and a replier creates the acknowledgment carried in every response, chooses that acknowledgment’s route, and may operate its first hop 𝑛 ACK . Figure 8 shows what the rewrap of Section 5.2 changes: 0 the exit keeps its route choice and the acknowledgment its format, but an adversary operating 𝑛 ACK receives the acknowledgment 0 header from the swap hop rather than from the client’s entry gateway.

A repository serves whatever inventory it holds once at least 𝑘 SURBs are available, and requests replenishment when a request cannot be met in full; outstanding replenishment requests expire after 60 s, so a service that missed one is retried rather than stranded.

17

Proceedings on Privacy Enhancing Technologies YYYY(X)

Mean Tload over three runs (s)

100

Constantinides et al.

The rewrap changes nothing else. The exit gateway keeps its route choice, the acknowledgment keeps its format, and the client keeps the SURB pool it already supplies; only the point at which the acknowledgment enters the mixnet moves out of the creator’s control.

= 2 KiB (n=118) = 5 KiB (n=118) = 10 KiB (n=118)

80 60

D.2

40

Between two addressed parties these attacks disclose nothing the address had not already given away. The case that matters is the one of Section 7.3: a client that withholds its own address and supplies the SURBs on which it will be answered, which makes the client the creator and the addressed party the replier, inverting the assignment of Section D.1 and leaving the client’s entry gateway as the only attachment point still hidden. Figure 9 shows how the rewrap keeps it hidden.

20 0 0

500

1000

1500

2000

2500

Fragments required by the page

Nym-Address Applications

3000

Figure 7: Page-load latency versus estimated fragment count after averaging each template over its three runs, yielding 118 points per payload size.

18

...

Proceedings on Privacy Enhancing Technologies YYYY(X)

L1

client’s S★ SURBs

L3

L2

3

1

Client

2

Entry gw

4

Exit gw

Web server

swap hop exit gateway builds the SURB-ACK 6

5

𝑛 ACK (adversarial) 0

client’s route: request

What 𝑛 ACK observes. The acknowledgment arrives from a mixnode in L3, 0 not from the client’s entry gateway. The client’s point of presence is not disclosed.

client’s route: response entry gateway’s outer shell exit gateway’s inner route

1. The client sends its request to the exit gateway, together with the SURBs on which it will be answered, over a route it selects itself. 2. The exit gateway retrieves the page from the clearnet web server. This link is not anonymised; the server sees the gateway and not the client. 3. The exit gateway returns the response on one of the client’s SURBs. As the replier it also constructs the SURB-ACK carried inside that response, and therefore chooses the acknowledgment’s route, including its first mix hop. 4. The client’s entry gateway extracts the SURB-ACK. Instead of injecting it on the route its creator chose, the gateway rewraps it in an outer shell of depth 𝐷 = 3 whose hops the gateway selects itself. 5. At the swap hop in L3 the outer header is consumed and the creator’s inner header is installed, so the acknowledgment leaves the shell and continues on the route the exit gateway chose. of that inner route may be operated by the exit gateway, which recognises the header it created. Its upstream neighbour is the layer-3 mixnode of 6. The first hop 𝑛 ACK 0 step 5 rather than the client’s entry gateway, so the observation the attack depends on is unavailable.

Figure 8: Replier-anonymous SURBs in clearnet browsing. Each hop is outlined in the colour of the party that selected it. The acknowledgment is the only route whose two halves have different owners, and because neither owner observes the other’s half, neither can recognise the packet as it enters the mixnet. We assume that a single fragment suffices for the request and for the response. Diagram drawn with AI assistance to the authors’ specification.

19

Proceedings on Privacy Enhancing Technologies YYYY(X)

Constantinides et al.

L1

client’s S★ SURBs

L3

L2

named by the address

address withheld 2

1

Client

Client’s gw

4

Holder’s gw

3

Address holder

swap hop holder builds the SURB-ACK 6

5

𝑛 ACK (adversarial) 0

client’s route: request

What 𝑛 ACK observes. The acknowledgment arrives from a mixnode in L3, 0 not from the client’s gateway. The client stays anonymous to a holder whose own address it knows.

client’s route: reply client gateway’s outer shell holder’s inner route

1. The client sends its request over a route it selects itself, whose last hop is the gateway named by the address. That gateway holds the correspondence between the address and the party attached to it, and forwards the request to the holder. The client supplies S★ SURBs in place of its own address, so its own gateway is never named. 2. The holder answers on one of those SURBs. Because the client supplied S★ SURBs, the holder cannot predict the ciphertext the reply presents at the last mix hop, which closes the companion attack of Section 5.1. 3. As the replier, the holder also constructs the SURB-ACK carried in that reply, and therefore chooses its route including the first mix hop 𝑛 ACK , which may be a mixnode 0 it operates. 4. The client’s gateway extracts the acknowledgment and rewraps it in an outer shell of depth 𝐷 = 3 whose hops the gateway selects itself. 5. At the swap hop in L3 the outer header is consumed and the holder’s inner header installed, so the acknowledgment continues on the route its creator chose. 6. 𝑛 ACK recognises the header it created, but its upstream neighbour is the layer-3 mixnode of step 5 rather than the client’s gateway. 0

Figure 9: Replier-anonymous SURBs when an anonymous client contacts a Nym-address holder. Roles are reversed with respect to Figure 8: here the client creates the SURBs and the addressed party replies on them. Both attacks a replier can mount against a creator land on the client’s gateway; S★ closes the last-mix-hop attack and the rewrap shown here closes the first-mix-hop attack on the acknowledgment. We assume that a single fragment suffices for the request and for the response. Diagram drawn with AI assistance to the authors’ specification.

20

Related documents

• Hidden Services Protocol for Mixnets#821273
• Point-to-Point Protocol: A proposal for multi-protocol transmission of datagrams over Point-to-Point links#131720
• Point-to-Point Protocol for the transmission of multi-protocol datagrams over Point-to-Point links#131758
• The Point-to-Point Protocol (PPP) for the Transmission of Multi-protocol Datagrams over Point-to-Point Links#136677
• Locator/ID Separation Protocol (LISP) Generic Protocol Extension#502669