PaperlayerView exact revision on arXiv

Source-linked AI summary

Hidden Services Protocol for Mixnets

Nicolas Constantinides, Mahdi Rahimi, Stavros Nonis

arXiv:2609.01326v1cs.CR

TL;DR

Existing mixnets protect sender anonymity but lack a secure, practical protocol for receiver privacy, especially against the sender. The paper develops defenses for two SURB-based endpoint attacks and builds NymHS, whose evaluation across 118 websites and 9,558 page loads shows that larger payloads substantially improve browsing performance.

  • Problem

    Existing mixnets lack a secure and practical protocol that simultaneously protects receiver privacy alongside sender anonymity.

  • Method

    The paper develops defenses against first- and last-mix-hop SURB attacks and implements NymHS with anonymous discovery, authenticated bidirectional sessions, and asynchronous SURB replenishment.

  • Results

    5.2x lower mean page-load latency and communication overhead reduced from 21.7% to 4.3% when increasing Sphinx payloads from 2 KiB to 10 KiB.

  • Takeaways & Limitations

    NymHS demonstrates that mutually anonymous hidden services can be implemented practically over mixnets with appropriately sized payloads.

  • Takeaways & Limitations

    The evaluation uses static pages from one public template repository, assumes lossless delivery, and runs in a controlled single-host environment rather than a geographically distributed deployment.

Abstract

from arXiv · show

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.2x and decreases communication overhead from 21.7% to 4.3% relative to the current Nym baseline.

1 Introduction

Mixnets protect sender anonymity by routing transformed, delayed packets through multiple mixnodes, but existing SURB use can expose either endpoint’s gateway under single-mixnode attacks. The paper introduces defenses and NymHS, then evaluates its practicality across large-scale web-browsing experiments.

  • Mixnets randomly delay and cryptographically transform packets across independently selected mixnodes, making input–output traffic correlation challenging.
  • Nym’s SURBs enable anonymous replies by letting a creator precompute a return path and provide routing information and encryption secrets to the replier.The replier encrypts application content, adds an acknowledgment SURB, and sends the packet through the return path.
  • Existing SURBs expose the replier’s gateway when a malicious creator controls the first mix hop and recognizes its unique routing token.The attack reveals the gateway upstream of the controlled first mixnode.
  • Existing SURBs expose the creator’s gateway when a malicious replier controls the final mix hop and matches the expected payload transformation.The replier receives all per-hop payload-key seeds, enabling this matching attack.
  • NymHS combines defenses against both attacks with authenticated publication, anonymous discovery, pseudonymous bidirectional sessions, and asynchronous SURB replenishment.The protocol routes both control and application traffic entirely through the mixnet.
  • 5.2x lower mean page-load latency and communication overhead reduced from 21.7% to 4.3% when Sphinx payloads increased from 2 KiB to 10 KiB.The evaluation covered 118 websites, 27 configurations, and 9,558 page loads.

3 Problem Statement and Malicious SURB Path Attacks

Standard SURBs permit two practical attacks when a malicious party controls one strategically placed mixnode, exposing a victim’s long-term gateway. Gateway discovery can enable deanonymization and active flooding, motivating defenses that preserve endpoint anonymity.

  • Threat and attack model: Standard SURBs do not protect endpoint anonymity when a malicious creator or replier additionally controls a single mixnode.The attacks are termed first-mix-hop and last-mix-hop attacks.
  • First-mix-hop attack: A malicious SURB creator can recognize a reply at a chosen first mix hop and expose the replier’s long-term entry gateway.The attack depends on controlling the selected first mixnode; protected inter-node links prevent a passive observer from reading the relevant traffic.
  • Last-mix-hop attack: A malicious replier and controlled last-layer mixnode can match payloads or seeds to identify a reply and reveal the creator’s gateway.The replier receives mix-derived seeds, enabling prediction of payload transformations or comparison with derived seeds.
  • Attack practicality: Repeated communication makes last-mix-hop recognition practical even though the replier cannot choose which of roughly 40 last-layer mixnodes is selected.Each fragment commonly consumes an independently routed SURB, creating repeated observation opportunities.
  • Consequences: Gateway discovery can enable later gateway compromise and Nym’s active flooding attack, which requires prior knowledge of the target gateway.NymHS prevents the gateway discovery needed to mount flooding against an otherwise anonymous endpoint but does not prevent flooding itself.
  • Design objective: The work strengthens SURBs against both attacks while preserving Sphinx compatibility and builds NymHS for mutually anonymous communication.The objectives address both malicious-path vulnerabilities and hidden-service communication without revealing either endpoint’s gateway.

4 Design Requirements

The protocol requirements target replier and mutual endpoint anonymity, authenticated asynchronous sessions, anonymous service discovery, and compatibility with existing Sphinx routing. The proposed SURB defenses conceal routing information and withhold mix-derived seeds while preserving packet-format compatibility.

  • Security requirements: R1 requires reply packets not to reveal the replier’s gateway, including against a creator controlling the first mix hop.The requirement covers both reply paths and SURB-ACK paths.
  • Security requirements: R2–R4 require anonymous service discovery, mutual endpoint anonymity, and authenticated bidirectional communication using pseudonymous identifiers.Clients should discover services using only a public pseudonym without exposing either party’s network attachment point.
  • Session requirements: R5 requires long-lived asynchronous bidirectional sessions that construct a fresh anonymous route for every packet.The design should avoid relying on persistent return paths while supporting interactive applications over extended periods.
  • Compatibility requirement: R6 requires preserving the Sphinx packet format and routing semantics, including standard mixnode header processing and probabilistic forwarding.The strengthened reply mechanism should not require modifications to the underlying routing protocol.
  • Last-mix-hop defense: The last-mix-hop defense withholds mix-derived seeds from the replier by embedding them in an onion-encrypted final routing block for gateway recovery.The gateway combines embedded seeds with its locally derived last-hop seed, while the replier no longer applies mix-derived payload encryption.
  • First-mix-hop defense: The first-mix-hop defense rewraps the reply on an independently selected outer route and swaps to the creator-provided inner header at a designated hop.This conceals the inner header until the swap hop, preserves the Sphinx header format, and leaves the resulting SURB representation 64 bytes smaller.
  • NymHS requirements and design: NymHS combines authenticated SURB publication, anonymous discovery, pseudonymous sessions, asynchronous bidirectional communication, and anonymous SURB replenishment through repository nodes.Repositories store precomputed SURBs without participating in end-to-end communication.

Roles in the Protocol

NymHS defines clients, hidden services, and repository nodes as distinct protocol roles, with all communication conducted through the mixnet. SURB creator and replier roles are independent of these protocol roles.

  • Protocol roles: A client initiates communication with a hidden service while concealing its network location.
  • Protocol roles: A hidden service receives and responds to client requests while concealing its network location.
  • Protocol roles: Repository nodes store and forward signed or encrypted SURBs exchanged by clients and hidden services.They do not serve as ordinary end-to-end communication participants; all entities communicate exclusively through the mixnet.
  • SURB terminology: Creator and replier identify roles on one SURB and can be held by either a client or a hidden service.A client creates SURBs for replies, while a hidden service creates SURBs that clients use to reach it.

SURB Publication and Verification

Hidden services publish authenticated SURBs to a deterministically selected repository set, where clients can retrieve fresh reply paths using the service’s public key. The public key acts as a stable, location-independent address without revealing the service’s gateway.

  • Publication: Before client communication, hidden services publish fresh SURBs to the repository layer.
  • Repository selection: The current network-wide epoch determines the selected repository set by selecting the N closest repository nodes.The epoch is a fixed-duration interval during which the Nym topology remains stable before refresh.
  • Publication contents: Each repository receives the service public key, a shared secret, and signed service SURBs through the mixnet.The SURBs support acknowledgments and replenishment requests.
  • Verification and storage: Repositories verify signatures, store valid SURBs indexed by the service public key, and return an acknowledgment using an auxiliary service SURB.Invalid publications are discarded and produce an error.
  • Location-independent addressing: A service public key provides a stable, location-independent address from which clients can derive the repository set and retrieve fresh reply paths.Clients can contact the service without learning its gateway or underlying network location.

SURB Retrieval by the Client

NymHS clients anonymously retrieve authenticated service SURBs through repository nodes, then use them to establish pseudonymous sessions and communicate bidirectionally. The protocol reserves capacity and supports asynchronous SURB replenishment when reply paths approach exhaustion.

  • SURB retrieval: Clients derive the repository set from the service public key and epoch, then anonymously send retrieval requests through the mixnet.A randomly selected repository receives the service key and auxiliary client SURBs for the response.
  • SURB retrieval: Repositories return at least k valid service SURBs through client-supplied auxiliary SURBs, while insufficient availability triggers an error and replenishment path.Retrieved SURBs are verified and stored locally for later communication.
  • Session establishment: Clients initiate sessions with ephemeral keys and authenticated requests, while pseudonymous session identifiers let services index state without learning network identities.The initial request includes bootstrap SURBs, and later requests carry continuation SURBs.
  • Asynchronous replenishment: Both endpoints reserve a threshold τ of SURBs; when a pool would fall below τ, communication is buffered and replenishment begins through a rendezvous identifier.Diffie–Hellman protects a newly generated SURB bundle stored at a selected repository and later retrieved anonymously.
  • Asynchronous replenishment: The requester decrypts the replenished SURBs and resumes communication, supporting asynchronous sessions without persistent circuits or fixed return paths.NymHS implements this protocol across client, hidden-service, and repository components as an extension of the Nym SDK.

6 Evaluation

The evaluation measures NymHS browsing latency and communication overhead while varying Sphinx payload size and rewrap depth in a controlled single-host experiment. Across 118 static websites and 9,558 page loads, larger payloads substantially improve latency and overhead, while deeper rewrapping adds modest latency.

  • Experimental setup: NymHS is benchmarked across 118 static websites under 27 configurations, with each configuration repeated three times for 9,558 page loads.The full-factorial design varies payload size ℓ from 2 to 10 KiB and rewrap depth D from 1 to 3.
  • Experimental setup: The single-host testbed isolates payload-size and rewrap-depth effects while avoiding public-network Sphinx incompatibilities and wide-area latency variability.All website resources are served locally, so every browser request traverses the mixnet.
  • Latency evaluation: Smaller payloads force more fixed-size fragments, whereas rewrap depth adds outer mix hops and processing without changing fragment count.Each additional rewrap layer peels a Sphinx layer, removes a POTP layer, and draws a mix delay.
  • Latency evaluation: At D=1, increasing ℓ from 2 KiB to 10 KiB reduces mean page-load latency from 36.06 s to 6.92 s, approximately 5.2× faster.Latency decreases at every payload increase and increases at every rewrap-depth increase; raising D from 1 to 3 adds 0.36–0.60 s.
  • Communication overhead: Fixed metadata consumes 21.7% of a 2 KiB packet but only 4.3% of a 10 KiB packet, raising sustained application throughput from 78.3 to 478.3 KiB/s.The Poisson schedule fixes the packet rate at approximately 50 packets per second, so larger payloads amortize metadata across fragments.
  • Limitations: The evaluation is limited to static pages, reliable delivery, and a controlled single-host environment, so packet loss and wide-area effects remain unmeasured.The authors state that geographically distributed deployments are needed to quantify realistic end-to-end latency.

7 Related Work

Related work spans mixnet, onion-routing, peer-to-peer, and metadata-private systems with different anonymity and rendezvous models. NymHS fills Nym’s prior hidden-service gap while addressing SURB attacks and supporting mutually anonymous service communication.

  • Prior mixnet systems: Sphinx and nymservers provide layered routing, constant-size packets, and pseudonymous SURB-based messaging, but not mutually anonymous client–service rendezvous or discoverable hidden services.NymHS extends the Loopix/Nym setting to provide that missing service model.
  • Hidden-service architectures: Tor and I2P support hidden services through persistent circuits or short-lived unidirectional tunnels, but their stated adversary and network architectures differ from Nym’s global-observer-oriented Loopix design.Nym uses independently routed Sphinx packets, probabilistic delays, continuous cover traffic, and stake-based Sybil resistance.
  • Applications on Nym: NymHS repairs Nym applications’ SURB vulnerabilities by preventing first- and last-mix-hop matching while preserving anonymous communication capabilities.The repaired configuration uses seed-free SURBs and gateway rewrapping of injected acknowledgments.
  • Mutual anonymity: Kerblam achieves mutually anonymous asynchronous messaging with two non-colluding servers, whereas NymHS builds on a decentralized Loopix/Nym mixnet.The systems therefore differ in their trust and deployment architectures.
  • Metadata-private messaging: Stadium protects metadata when communicating parties already know one another’s identifiers, while NymHS adds anonymous service discovery and mutually anonymous client–service communication.The two systems address different communication models.
  • Applications on Nym: Pudding provides private user discovery but does not address SURB-ACK attacks, and its discovery servers retain reachability information linked to entry gateways.The supplied analysis reports that a compromised recognizing mix node can distinguish registered from unregistered identifiers under the prototype behavior.

8 Conclusion

The paper develops NymHS to provide simultaneous sender and receiver anonymity in mixnets, addressing attacks arising from naive SURB use. Its implementation and evaluation show that mutually anonymous hidden services can operate practically over mixnets.

  • Standard SURBs enable two single-mixnode attacks that expose the other party’s long-term gateway.A malicious creator can exploit first-hop matching, while a malicious replier can exploit last-hop payload matching.
  • The proposed defenses address both first-mix-hop and last-mix-hop attacks.
  • NymHS provides authenticated SURB publication, anonymous service discovery, pseudonymous sessions, asynchronous bidirectional communication, and SURB replenishment.The protocol requires only limited changes to the underlying mixnet, including the POTP payload format and three routing flags.
  • 9,558 page loads across 118 websites show that reply fragmentation dominates page-load latency.Reducing the payload size from 10 to 2 KiB increases mean page-load latency by 29.1 s.
  • The experiments support practical deployment of mutually anonymous hidden services over mixnets with appropriately sized payloads.

A Sphinx and SURB Construction Details

This appendix describes Sphinx’s fixed-size, layered packet and header construction, including recursive routing-block masking, integrity protection, and filler generation for variable route lengths.

  • The construction derives per-hop streams and payload-key seeds from shared secrets using keyed derivation functions.The payload key is obtained by hashing each payload-key seed.
  • With Nym’s parameters of κ = 128 bits and r = 5, the on-wire Sphinx header is 348 bytes.
  • Sphinx headers combine an ephemeral Diffie–Hellman element, an encrypted routing block, and a header-integrity tag.The accompanying payload is layered-encrypted, and padding maintains fixed packet size.
  • Per-hop metadata contains forwarding information, routing flags, and destination-related fields, with a shorter final-hop format.Routing flags include FORWARD, FINAL, SWAP_HEADER, and EMBEDDED_KEYS.
  • Filler strings recursively pad routing blocks to fixed length rη regardless of the actual route length ν.Figure 3 illustrates this construction for ν = 4 and r = 5.
  • Each routing-block row XOR-masks routing metadata with head(ρ_i) and authenticates the resulting block with γ_i.Figure 4 illustrates the construction for ν = 4, r = 5, and |Δ| = 2κ.

A.3 Pudding Deterministic SURB Generation

The appendix details deterministic SURB generation and the modified final routing block used to withhold mix-derived payload seeds from repliers while preserving gateway processing.

  • Pudding deterministically derives SURB randomness and routes from KDF(nonce ∥ ID ∥ k).The queried identifier, lookup nonce, and discovery-node secret are the entropy inputs.
  • Nym uses five routing blocks for ordinary four-hop reply paths, leaving one unused routing step in the final block.
  • The modified construction embeds prior-hop payload-key seeds K_emb = σ_0∥σ_1∥⋯∥σ_{ν−2} in the final routing block.The final-hop flag is set to EMBEDDED_KEYS, replacing part of the random filler.
  • Only the gateway can recover the embedded seeds because they remain inside the onion-encrypted final routing block.
  • The replier receives the modified SURB and sends the packet without applying the mix-derived layers.The gateway recovers the embedded seeds, processes its own layer, forwards the clear SURB acknowledgment, and delivers the encrypted fragment to the client.
  • Because the replier never learns the mix-derived seeds, it cannot predict the last-hop payload ciphertext for matching.

B Implementation Details

The prototype realizes NymHS through separate client, hidden-service, and repository binaries, modifies the Sphinx layer, and evaluates page-load behavior across controlled configurations.

  • The prototype comprises client-proxy, hidden-service, and repository-node binaries with distinct session, publication, storage, and proxying roles.
  • NymHS replaces the payload permutation with length-preserving AES-128-CTR POTP and adds three routing flags.A high flag bit additionally requests per-hop tracing for debugging.
  • At ν = 4, an S★SURB is 396 B, compared with 460 B for Nym’s seed-carrying SURB.The 64 B difference corresponds to mix-derived seeds moved into final-hop padding.
  • Each repository publication uses a fresh 128-bit shared secret, and republication requires a matching secret rather than an envelope signature alone.
  • The repository serves available SURBs once at least k are held and requests replenishment when a request cannot be fully met.Outstanding replenishment requests expire after 60 s and are retried if missed.
  • Figure 6 plots page-load latency against estimated fragment count for D = 1, with points for 118 templates across three runs and least-squares fit lines.

C Latency and Fragment Count

Page-load latency is closely tied to estimated Sphinx fragment count, while fixed-granularity effects and SURB replenishment rounds explain remaining variation. Rewrapping preserves the acknowledgment’s route and format while moving its entry point out of the creator’s control.

  • Latency and Fragment Count: Latency is approximately linear in estimated fragment count across payload sizes.The fragment estimate divides returned bytes by the application data carried per fragment, but is a lower bound because resources fragment independently.
  • Latency and Fragment Count: 30.6, 27.5, and 28.2 ms are the fitted per-fragment slopes at 2, 5, and 10 KiB, respectively.The corresponding page-load models are approximately 7.9 + 0.031F seconds at 2 KiB and 2.7 + 0.028F seconds at 10 KiB.
  • Latency and Fragment Count: Averaging templates over three runs reduces 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.The remaining residual is attributed mainly to per-response fragmentation granularity and fixed-cost rendezvous replenishment rounds.
  • Rewrapping: The rewrap leaves the exit’s route choice, acknowledgment format, and client SURB pool unchanged.It changes only where the acknowledgment enters the mixnet, moving that point out of the creator’s control.
  • Rewrapping: In anonymous-client browsing, the client’s gateway rewraps the acknowledgment in an outer depth-3 shell before the holder’s inner route is restored.At the swap hop, the outer header is consumed and the holder’s acknowledgment header is installed; the acknowledgment’s first mix hop then sees a layer-3 upstream neighbor rather than the client’s gateway.
Loading 2609.01326v1…