A traffic analysis attack against Introduction Protocol and Onion Services

arXiv:2602.23560 · cs.CR · Submitted 2026-02-27 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia, and with me are Elias and Priya, guest researcher.

Elias: Today's paper: "A traffic analysis attack against Introduction Protocol and Onion Services".

Nadia: Tor onion services rely on long-lived introduction circuits to support anonymous rendezvous between clients and services, and although Tor incorporates defenses against traffic analysis,

Elias: First, who's behind it and why it matters.

Title and authors: Nadia: So, to summarize what the paper is actually doing in "A traffic analysis attack against Introduction Protocol and Onion Services," they are presenting a practical intersection attack designed to find every hop in a Tor introduction circuit by observing traffic only at one relay per stage.

Elias: It boils down to repeatedly probing the target service and intersecting sets of observed destination IP addresses within those INTRODUCE1–RENDEZVOUS2 intervals, which lets them identify the next relay with certainty at each step until they pinpoint the service location.

Priya: What I find interesting about this summary is how they frame it—it’s not about a single lucky observation; it’s a systematic, iterative process that exploits the protocol's deterministic routing to systematically prune candidate relays.

Nadia: That systematic pruning is what makes it so powerful; they show how, given the specific properties of introduction circuits, an adversary can progressively shrink the anonymity set until only one relay remains for each hop.

Elias: They are highlighting that this attack doesn't need global visibility or access to packet payloads; it only requires observing traffic at a single monitored relay during those short protocol intervals to identify successors.

Priya: That constraint is really important because it grounds the attack in observable network behavior, which is what we measure and analyze, rather than just assuming perfect secrecy everywhere.

Nadia: Right, and they emphasize that this technique reveals a specific gap in Tor’s privacy model—a vulnerability stemming from the deterministic structure that resists traffic analysis intended to hide observation points.

Elias: It suggests the current defense against traffic analysis might be insufficient if it doesn't account for these inherent structural dependencies within the introduction protocol itself.

Priya: If this is accurate, then future research needs to focus on how we can design circuits or protocols that introduce more randomness or variability into those critical path selection mechanisms to thwart this kind of intersection attack.

The paper's summary: Nadia: Moving on to the suggested improvements in "A traffic analysis attack against Introduction Protocol and Onion Services," the authors aren't just pointing out the flaw; they are suggesting ways to enhance anonymity by looking beyond just protocol structure.

Elias: They are proposing that we need to move away from relying solely on cryptographic security or statistical inference for privacy, and instead integrate a structural awareness of underlying protocols like onion routing circuits to find these deterministic vulnerabilities.

Priya: That connects back to my earlier point; it suggests that defenses shouldn't just be about adding more math or better statistics; they need to actively model the protocol's execution flow itself.

Nadia: They also suggest implementing "Structural Anonymity Set Reduction" algorithms that use those specific protocol execution intervals, like INTRODUCE1–RENDEZVOUS2, along with intersection logic, to progressively prune candidates with high confidence.

Elias: That sounds like a direct response to their attack; if you can model the set reduction based on the known protocol timing, you might be able to neutralize the iterative shrinking process described in their methodology.

Priya: And then there’s this idea of developing adaptive traffic analysis detection systems that look for recurring pattern intersections across multiple short intervals instead of just waiting for a single anomalous event to occur.

Nadia: That shift from looking for a one-off event to monitoring recurring intersections seems like a practical step toward building more robust defenses against this type of systematic attack.

Elias: It points toward defenses that have temporal awareness, understanding that the protocol operates in discrete, time-bound stages where patterns can be tracked over those intervals.

Priya: So, the suggestion is to make our detection systems smarter about the timing and repetition inherent in how these anonymous communication networks operate rather than treating every observation as a completely new event.

The paper's improvements: Nadia: So we've talked about how "A traffic analysis attack against Introduction Protocol and Onion Services" demonstrates a practical method for hop-by-hop identification using intersection attacks based on the deterministic nature of introduction circuits.

Elias: We established that this attack exploits the fixed relationship between relays during specific protocol intervals to shrink anonymity sets down to a single candidate, revealing a gap in Tor’s privacy model.

Priya: My main thought is that this work provides concrete evidence of how protocol design choices directly translate into exploitable structural weaknesses in anonymity systems.

Nadia: It definitely shows that relying only on cryptographic strength isn't enough when the underlying routing mechanism has predictable patterns that can be analyzed over time.

Elias: And the proposed improvements suggest a path forward by demanding structural awareness and temporal modeling in both our theoretical models and our detection algorithms to counter this kind of attack effectively.

Priya: I feel that this paper moves us closer to a more holistic understanding of anonymity, where we consider the protocol structure as an active component in the security analysis, not just a passive container for encryption.

Nadia: Indeed, this work on "A traffic analysis attack against Introduction Protocol and Onion Services" is really showing us that even well-designed systems have specific structural vulnerabilities that require specialized analytical tools to uncover.

Elias: It’s a reminder that the battle for anonymity isn't just about stronger math, but about understanding how the system behaves when subjected to repeated, structured observation.

Priya: It’s a solid piece of research that really highlights where we need to focus our efforts in the next phase of privacy research.

Nadia: That’s all for this paper; thanks to Elias and Priya for bringing the technical depth and the practical measurement perspective to this discussion on "A traffic analysis attack against Introduction Protocol and Onion Services."

Conclusion: Nadia: So, we've just walked through "A traffic analysis attack against Introduction Protocol and Onion Services," which shows how deterministic routing in Tor circuits can be exploited to map out every hop of an onion service.

Elias: Yeah, that's exactly what the paper demonstrates: how repeated observation during specific protocol windows allows for a methodical reduction of the anonymity set until a single relay is identified at each stage.

Priya: What really stands out from my perspective is how they ground this attack in real-world network behavior using live experiments under varying traffic conditions, which gives us actual data to look at.

Nadia: I agree, Priya; seeing it proven in a controlled Tor environment makes the implications feel much more tangible than just theoretical security discussions.

Elias: From a cryptographic standpoint, the proof hinges on that INTRODUCE1–RENDEZVOUS2 interval being long enough and deterministic enough for that intersection logic to work reliably across multiple trials.

Priya: That determinism is key because it means the adversary doesn't have to guess; they can systematically probe and gather data across those defined time boundaries.

Nadia: And the implication for us, as security researchers, is that we need to look at circuit construction not just for encryption strength, but for these inherent structural properties that might invite this kind of traffic analysis.

Elias: Precisely; it pushes us to consider how protocol parameters influence the observable traffic patterns over time.

Priya: I think the real impact here is showing that a focused, coordinated adversary could realistically deploy this if they have some level of global observation capability, which is a sobering thought for privacy engineers.

Nadia: It certainly gives us something concrete to discuss in our next sessions about designing more robust circuits that actively resist these systematic structural probes.

Elias: We're definitely going to be looking at how we can introduce more variability or noise into the path selection process to break that deterministic link.

Priya: I hope this paper inspires us all to think about measurement and temporal patterns as crucial defenses in the fight for anonymity online.

Department of Computer Science, University of Cyprus · CYENS - Centre of Excellence, Cyprus

cs.CR

Submitted: 2026-02-27

Updated: 2026-09-28

Comments: New paper with minimal overlap will be submited as a new paper

Code: https://github.com/nick1231321/tor-introduction-intersection

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 79/100

The gist: Tor onion services rely on long-lived introduction circuits to support anonymous rendezvous between clients and services, and although Tor incorporates defenses against traffic analysis, "the

Key concepts

Traffic Analysis Attack
A practical method where an adversary identifies every hop in a Tor introduction circuit by observing traffic only at one relay during short protocol intervals. This is achieved by repeatedly probing the service and intersecting observed destination IP addresses to pinpoint the next relay with certainty at each step.
Introduction Circuit
The circuits used by Tor onion services that rely on long-lived introduction circuits to support anonymous rendezvous between clients and services. The paper exploits the deterministic routing within these circuits, which allows an adversary to systematically prune candidate relays.
Structural Anonymity Set Reduction
A suggested improvement where algorithms use specific protocol execution intervals, such as INTRODUCE1–RENDEZVOUS2, along with intersection logic. This method aims to progressively prune candidate relays with high confidence by modeling the protocol's structural execution flow.
Temporal Awareness in Defenses
The need for detection systems to look for recurring pattern intersections across multiple short intervals rather than just a single anomalous event. This shift requires defenses to be smarter about the timing and repetition inherent in how anonymous communication networks operate.

Terminology

Summary

Tor onion services rely on long-lived introduction circuits to support anonymous rendezvous between clients and services, and although Tor incorporates defenses against traffic analysis, the introduction protocol retains deterministic routing structure that can be exploited by an adversary. The paper presents a practical intersection attack against Tor introduction circuits that can identify each hop from the introduction point toward the onion service while requiring observation at only one relay per stage. This attack repeatedly probes the target service and intersects sets of destination IP addresses observed within narrowly bounded INTRODUCE1–RENDEZVOUS2 intervals, without assuming global visibility or access to packet payloads. The traffic-analysis technique identifies "with certainty the next relay in the path to target at each stage, thereby revealing a gap in Tor’s privacy model, which is intended to resist traffic-analysis attacks in which an adversary uses traffic patterns to determine which points in the network to observe or attack."

The work makes several contributions:

- We identify deterministic structural properties of introduction circuits that can be exploited by an adversary.

- We show that these properties enable an intersection attack capable of identifying successor hops of a relay in an introduction circuit.

- We demonstrate the feasibility of the attack through live Tor-network experiments conducted under varying background traffic conditions using a self-operated onion service.

- We evaluate the practical implications of the attack, arguing that coordinated state-level adversaries could realistically deploy it given the concentration of relay consensus weight in Fourteen Eyes countries.

The goal is to establish the feasibility of the attack rather than to design or evaluate defenses. The paper focuses on demonstrating convergence in practice.

Background and Preliminaries:

Onion routing forwards traffic through multiple relays such that no single relay learns the full communication path. Tor supports onion services, which enable clients and servers to communicate without revealing their IP addresses, underpinned by the introduction protocol (to signal intent) and the rendezvous protocol (to establish an anonymous bidirectional channel). Publishing an Onion Service involves selecting three relays as introduction points, constructing long-lived circuits to these points, and uploading a signed descriptor containing its introduction points. Client access involves retrieving this descriptor, selecting a rendezvous point, and sending an INTRODUCE1 cell containing the rendezvous point identifier. The service then encapsulates this into an INTRODUCE2 cell for forwarding to the hidden service over the pre-established introduction circuit.

Anonymity Set and Intersection Attacks:

An anonymity set is defined as the set of entities that an adversary cannot distinguish as potential sources or recipients of an observed action, given the observation and any auxiliary information available. If an adversary observes traffic at a monitored relay rm on an introduction circuit during the INTRODUCE1–RENDEZVOUS2 interval, any node that receives traffic from rm within ∆t is a candidate for the next hop, defining the successor’s anonymity set as A = the set of ni ni receives traffic from rm during ∆t. Intersection attacks reduce anonymity by repeatedly observing these sets and computing their intersection: "if each trial yields an anonymity set At that contains the true element x, an adversary computes It = Σj=1 Aj, which forms a monotonically shrinking sequence of sets. Once It = 1, the adversary identifies x with high confidence." This attack leverages short-term, protocol-level observations during each execution of the introduction protocol.

Attack Motivation and Problem Statement:

The attack is motivated by four properties: persistence of introduction circuits (longer than ordinary Tor circuits), circuit churn and large path space (causing background traffic to change across trials), short execution time of the introduction protocol (0.5–1.5 seconds for INTRODUCE1–RENDEZVOUS2), and introduction protocol determinism (During every INTRODUCE1–RENDEZVOUS2 interval, the successor relay in the introduction circuit must exchange traffic with the monitored relay). The problem statement is to determine "whether an adversary can, by repeatedly collecting the set of IP addresses that exchange traffic with a monitored relay during successive INTRODUCE1–RENDEZVOUS2 intervals, 1. progressively shrink the successor relay’s anonymity set until only one candidate remains, and 2. iteratively apply this procedure to identify every hop in the introduction circuit and ultimately recover the hidden service’s network location."

Attack Methodology:

The attack proceeds iteratively over four stages, where each stage k targets a single unknown relay. The steps involve establishing a rendezvous point and transmitting an INTRODUCE1 cell, monitoring outbound traffic at the monitored relay until RENDEZVOUS2 response is received, recording the anonymity set A(k)t, removing the predecessor relay from it if k > 1, and computing the cumulative intersection I(k)t = I(k)t-1 ∩ A(k)t. The stage terminates when I(k)t = 1, at which point the successor relay is identified.

Improvements for AI systems

As an excellent, fastidious, and diligent researcher, I have analyzed this paper on A traffic analysis attack against Introduction Protocol and Onion Services. The core finding is that the deterministic structure of Tor's introduction circuits allows for a practical intersection-based traffic analysis attack to identify successor hops hop-by-hop.

Based on this research, here are the specific improvements we can implement in AI systems:

)

Improved AI System Capabilities:

  1. Do not rely solely on cryptographic security or statistical inference for privacy preservation; instead, integrate structural awareness of underlying protocols (like onion routing circuits) to identify deterministic vulnerabilities.

  2. Implement Structural Anonymity Set Reduction algorithms that leverage protocol execution intervals (like the INTRODUCE1–RENDEZVOUS2 window) and intersection logic to progressively prune candidate sources or destinations with high certainty, even under partial-visibility adversary models.

  3. Develop adaptive traffic analysis detection systems that monitor for recurring pattern intersections across multiple short intervals, rather than looking for single, anomalous events.

Specific Improvements:

Specific AI System Functionality:

Abstract

Tor onion services rely on long-lived introduction circuits to support anonymous rendezvous between clients and services. Although Tor incorporates defenses against traffic analysis, the introduction protocol retains deterministic routing structure that can be exploited by an adversary. We present a practical intersection attack against Tor introduction circuits that over repeated interactions can identify each hop from the introduction point toward the onion service while requiring observation at only one relay per stage. The attack repeatedly probes the target service and intersects sets of destination IP addresses observed within narrowly bounded INTRODUCE1-RENDEZVOUS2 intervals, without assuming global visibility or access to packet payloads. Our traffic-analysis technique identifies with certainty the next relay in the path to target at each stage, thereby revealing a gap in Tor's privacy model, which is intended to resist traffic-analysis attacks in which an adversary uses traffic patterns to determine which points in the network to observe or attack. We evaluate the attack's feasibility through live-network experiments using a self-operated onion service and relays. To support data minimization, we implement a Tor-compatible plugin that computes intersections online over pseudonymized data retained only in volatile memory. Our experiments show reliable convergence in practice, with convergence rate influenced by relay consensus weight and time-varying background traffic. We further assess practicality under a partial-global adversary model and discuss the implications of geographic concentration in Tor relay selection weight across cooperating jurisdictions.

Sources

Related papers