Flow Correlation Attacks on Tor Onion Service Sessions with Sliding Subset Sum

Flow Correlation Attacks on Tor Onion Service Sessions with Sliding Subset Sum

Speakers: Daniela Lopes

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=3I9Z5CvyBR4

Overview

In a significant presentation at the NDSS Symposium, Daniela Lopes unveiled SUMo, a novel and highly effective flow correlation attack specifically engineered to deanonymize Tor onion service sessions. Tor, widely lauded as a critical low-latency anonymity network, provides essential client-side and server-side anonymity, particularly through its onion services which allow service providers to operate discreetly without revealing their physical network locations. This research directly challenges the perceived anonymity guarantees of these services by demonstrating the practical feasibility of linking a client's Tor traffic to the underlying IP address of the onion service it accesses.

The core problem addressed by SUMo is the vulnerability of Tor onion services to flow correlation, an attack fundamentally distinct from website fingerprinting. While website fingerprinting can infer which .onion address a user visits, it cannot uncover the service's IP address. Flow correlation, in contrast, aims for full endpoint deanonymization by analyzing and correlating timing patterns and packet volumes across different points of a Tor circuit. Prior flow correlation methods, such as DeepCorr and DeepCoFFEA, primarily targeted Tor traffic destined for clearnet websites and often struggled with the unique characteristics of onion service traffic, including session multiplexing and performance bottlenecks.

SUMo introduces a sophisticated, distributed pipeline architecture that overcomes these limitations. It combines advanced machine learning classifiers for intelligent traffic filtering with a novel similarity function based on the classic subset sum decision problem for precise session matching. The research demonstrates how a coalition of Internet Service Providers (ISPs), acting as a global passive adversary, could deploy SUMo to efficiently and effectively deanonymize onion service sessions. This work not only exposes a critical vulnerability but also provides a robust framework for understanding and mitigating such sophisticated traffic analysis attacks against Tor.

Background

▶ Watch: Introduction to SUMo and the onion service deanonymization problem (0:00)

Tor, or The Onion Router, operates as a distributed, multi-hop overlay network designed to provide anonymity for its users. A typical Tor circuit consists of three relays: a guard node, a middle node, and an exit node. User data is encapsulated into fixed-sized onion-encrypted cells and routed through this circuit, making it difficult to trace the origin and destination of traffic. Onion services extend this anonymity to servers, allowing them to host services without revealing their IP addresses. The connection process for an onion service involves the service advertising its presence through introduction points, which clients then query. A client and the onion service then establish independent circuits to a chosen rendezvous point, ensuring mutual anonymity.

Despite these privacy mechanisms, Tor is susceptible to various traffic analysis attacks. One of the most studied categories is website fingerprinting, where an adversary monitors traffic between a Tor client and its guard node. By matching observed traffic patterns to pre-recorded "fingerprints" of known onion services, an attacker can infer which service a user is visiting. However, website fingerprinting has significant limitations: it cannot deanonymize the IP address of the onion service, it requires pre-existing fingerprints for known services, and ambiguities can arise from mirror sites or dynamic content.

This talk focuses on flow correlation attacks, a more potent form of traffic analysis. These attacks aim to link a flow entering the Tor network with a corresponding flow exiting it, thereby deanonymizing the IP addresses of the communicating endpoints. This is achieved by correlating metadata such as packet volumes and inter-packet timing observed at different network vantage points, typically requiring an adversary to monitor both guard and exit nodes, often as colluding ISPs. Flow correlation offers several advantages over website fingerprinting: it eliminates the need for prior knowledge of specific onion services, directly unmasks server IP addresses, and adapts to changes in website content.

However, applying existing flow correlation techniques, which were primarily designed for clearnet traffic, to Tor onion services presents unique challenges. First, Onion Traffic Classification Challenges arise because onion service sessions have distinct traffic characteristics. Within Tor tunnels, packets are manipulated to fit fixed-sized cells, leading to different packet size distributions compared to clearnet traffic, which is unpacked and sent over HTTP(S). Crucially, a single onion service can establish concurrent sessions with multiple clients, leading to multiplexed traffic over the same TLS connection between the onion service and its guard node, which can severely degrade correlation accuracy for techniques assuming one-to-one flow correspondence. Second, Performance and Maintainability Challenges are significant. Deep learning-based classifiers, common in prior work like DeepCoFFEA, are computationally intensive, making large-scale correlation impractical due to the vast number of possible client-server pairs. Furthermore, these models require frequent updates and extensive data collection as traffic patterns evolve. Third, the Base Rate Fallacy Challenges the effectiveness of classifiers. The vast disproportion between clearnet and onion service traffic volumes means a classifier not specifically calibrated for this imbalance might frequently misclassify clearnet traffic as onion service traffic, drastically reducing its real-world utility.

To address the base rate fallacy for onion service traffic, prior work by Kwon et al. introduced circuit fingerprinting, a technique to distinguish Tor client and onion service entry guard connections and filter out clearnet traffic. However, this method was rendered ineffective in 2019 with Tor version 0.4.1.5, which integrated padding cells during circuit establishment, making cell counting difficult. SUMo responds to this by developing an updated, robust circuit fingerprinting technique as a preliminary filtering stage.

The threat model for SUMo assumes a global passive adversary, realistically embodied by a coalition of ISPs. These colluding ISPs are capable of intercepting traffic at Tor guard nodes and correlating flow pairs from the same onion service session. They can monitor all traffic within and across their networks, collecting per-packet metadata such as source/destination IP and port, packet size, and packet arrival time, without needing to inspect payload. The adversary is computationally bounded, cannot break Tor's cryptographic schemes, nor actively manipulate traffic (e.g., drop, delay, inject packets). The attack's coverage depends on the number of monitored guard nodes, with the research focusing on demonstrating feasibility within a specific time window, acknowledging the substantial resources continuous operation would demand.

Key Findings

▶ Watch: Tor onion services and website fingerprinting limitations (2:00)

The research on SUMo yielded several critical findings that underscore the feasibility and effectiveness of flow correlation attacks against Tor onion services:

• Novel and Highly Effective Attack: SUMo is presented as a novel, effective, and efficient flow correlation attack specifically designed for deanonymizing Tor onion service sessions, addressing limitations of prior clearnet-focused methods.
• Near-Perfect Correlation for Longer Sessions: Under ideal conditions (perfect filtering), SUMo achieves a remarkable 99.64% precision and 99.65% recall for correlating sessions of any duration. For sessions lasting longer than 6 minutes, SUMo achieves 100% precision and 100% recall, demonstrating near-perfect accuracy for sustained interactions.
• Robust Filtering Phase: The preliminary filtering phase, comprising Source Separation and Target Separation machine learning classifiers, exhibits extremely high accuracy. The Source Separator achieves an average precision (AP) of 1.0, while the Target Separator, after hyperparameter tuning, reaches an AP of 0.99. This robust filtering is crucial for mitigating the base rate fallacy.
• High Precision and Recall in Full Pipeline: When the full SUMo pipeline is evaluated with imperfect (ML-guided) filtering, it still achieves 99.5% precision and 89.6% recall for sessions of any duration. For sessions exceeding 6 minutes, precision further improves to 99.76% and recall to 92.07%.
• Superior Performance over State-of-the-Art: SUMo significantly outperforms DeepCoFFEA, a leading flow correlation attack for Tor clearnet circuits, when applied to onion service traffic. SUMo is approximately two orders of magnitude faster, achieving a peak throughput of 153,000 flow pairs/s compared to DeepCoFFEA's 1,639 flow pairs/s, and is more memory-efficient, consuming only 450MB of GPU memory compared to DeepCoFFEA's 2,100MB.
• Resilience to Concurrency: SUMo successfully correlates browsing sessions even under high levels of concurrency, where popular onion services experience over 10 concurrent sessions. While highly popular onion services contribute to more false positives, the attack remains effective.
• Identification of Vulnerable Session Characteristics: The research reveals that short browsing sessions (typically less than 6 minutes, with 8 or fewer requests, and mostly under 3 requests) are the primary source of false positives and represent the most challenging scenarios for accurate correlation. This suggests that longer, more data-intensive sessions are particularly vulnerable.
• Feasibility of IP Deanonymization: The overall findings definitively demonstrate the practical feasibility of an adversary, such as a coalition of ISPs, deanonymizing the IP addresses of Tor onion service sessions.

Technical Deep Dive

▶ Watch: Identifying key challenges for onion service flow correlation (4:00)

The SUMo attack is meticulously engineered to overcome the inherent challenges of flow correlation against Tor onion services, leveraging a distributed, pipelined architecture. The system is composed of two primary components: probes and a correlator.

Probes are strategically deployed network devices within the colluding ISPs. Their function is to intercept network traffic, gather per-packet metadata (source/destination IP, port, packet size, arrival time), and pre-process this data. This pre-processing involves discerning whether a flow originates from the client-side or the server-side of an intercepted onion service session. For instance, a probe monitoring a client's guard node would capture the client-side flow, while another probe monitoring the onion service's guard node would capture the server-side flow.

The correlator receives the pre-processed flow metadata from the probes. Its core task is to identify pairs of client-side and server-side flows that correspond to the same onion service session. Upon successful identification, the correlator produces session records detailing client and server IP addresses, flow pair metadata, and a similarity score. The correlator can be hosted on ISP-managed servers or a third-party cloud provider and is designed to handle specific deanonymization queries, allowing an attacker to narrow down the search space by specifying ISPs, IP address ranges, or time windows.

System Design and Architecture - Pipeline Phases

SUMo employs a distributed pipeline architecture to enhance scalability and optimize traffic analysis. This pipeline consists of two online phases and one offline training phase:

1. Offline Training Phase: This initial phase is crucial for training and validating the machine learning classifiers used in the filtering phase. It also involves fine-tuning hyperparameters for both filtering and matching components, ensuring optimal performance and generalization.

1. Online Filtering Phase (Executed by Probes): This phase is implemented by the network probes and acts as a crucial preliminary step to mitigate the base rate fallacy. Each probe uses a packet sniffer and feature extractor (implemented with scapy) to generate a feature vector for every observed flow. This phase involves two key stages, both utilizing lightweight XGBoost gradient boosting decision tree classifiers (leveraging scikit-learn and xgboost Python libraries), with hyperparameters optimized via Bayesian optimization using the hyperopt library:

• Source Separation (Step 1): The objective here is to accurately distinguish flows originating from a Tor client from those originating from an onion service. Prior research has identified distinct network connection patterns for these flow types, which remain evident in current Tor versions. Clients typically send smaller traffic volumes and receive larger volumes compared to onion services. The model is trained on summary statistics derived from flow packet lengths, inter-arrival times, and burst behavior. Top features include incoming burst bytes (at 40th, 50th, 60th, and 70th percentiles) and outgoing packet sizes (at 80th percentile). This classifier achieved an impressive Average Precision (AP) of 1.0.
• Target Separation (Step 2): This stage, applied only to flows already classified as client-originated, aims to filter out client flows directed to clearnet websites, leaving only those targeting onion services. Differences captured include longer circuit durations, higher latency, and more packet reordering for onion service circuits, contrasted with shorter durations and larger bursts for clearnet requests. Onion service pages also tend to have fewer resources. Top features for this stage include outgoing packet times (at 20th and 30th percentiles), incoming burst bytes (at 40th and 50th percentiles), and outgoing max burst. This classifier achieved an AP of 0.99 after tuning.

1. Online Matching Phase (Executed by Correlator): This phase takes the filtered client and onion service flows and attempts to correlate them pairwise. The core of this phase is the novel Sliding Subset Sum algorithm:

• Pair Concurrent Flows (Step 3): To optimize efficiency, the algorithm first identifies candidate flow pairs by considering only onion service flows that temporally overlap with a given client flow. Flows are divided into epochSize second time epochs, with an epochTolerance allowance for temporal shifts.
• Bucketizing Each Flow Pair (Step 4): For each candidate flow pair, packets received during the client flow's interval are grouped into fixed tsInterval buckets (e.g., 0.5 seconds). The same process is applied to the onion service flow. Coarser-grained time units were empirically found to yield better results, compensating for Tor's multi-hop network delays and reordering.
• Computing the Sliding Subset Sum (Step 5): This is SUMo's core volumetric flow similarity algorithm, implemented in C++ for performance and wrapped with ctypes for Python integration. It aggregates buckets into windows (defined by bktsPerWindow). For each window, a Subset Sum Similarity Score is computed. This is a variation of the classical subset sum problem: given a set of positive integers A (representing onion service sent packet buckets) and a positive integer M (representing the client received packet sum in the same window), it searches for a subset of A whose sum equals M. To account for network noise, packet delays, and reordering, SUMo allows for a range M - Δ to M + Δ. Windows are scored as 1 for a match, -1 for no match, or 0 if neither flow sends/receives packets. The window then slides by bktsOverlap buckets until the entire flow pair is processed, resulting in a vector of window scores. For computational efficiency, the algorithm primarily focuses on packets flowing from the onion service to the client.
• Final Flow Pair Correlation Decision (Step 6): The individual window scores are adjusted to emphasize consecutive matches (score 1) or non-matches (score -1) using a parameter K (set to 0.1). The final similarity score S(fc, fon) for a flow pair is the average of these adjusted window scores. The algorithm then selects the flow pair with the highest S(fc, fon) among all candidates. If this highest score exceeds a predefined threshold (thr), the pair is declared correlated; otherwise, it's non-correlated. The thr parameter balances precision and recall.
• Implementation details for the Matching Phase include using OpenCL 3.0 for GPU support, enabling Single Instruction Multiple Data (SIMD) parallelism to process multiple flow pairs and multiple windows simultaneously. Hyperparameter tuning for this phase also utilized hyperopt, aiming to maximize the F1-score.

Demo / Proof of Concept

▶ Watch: Addressing the base rate fallacy in onion service analysis (5:40)

While the talk does not describe a live, interactive demonstration in the traditional sense, the research extensively details the construction and evaluation of an open-source prototype of SUMo. This prototype, comprising approximately 5500 lines of Python code, along with specific C++ and OpenCL components, serves as a robust proof of concept for the attack's feasibility.

The experimental testbed for evaluating SUMo's capabilities was highly realistic and distributed. It consisted of 48 virtual machines (VMs) configured as onion services and 60 VMs acting as Tor clients, geographically distributed across 14 distinct locations worldwide on Google Cloud (cos-101-1ts instances). Onion services and clients ran Tor version 0.4.7.10 within isolated Docker containers. Clients used selenium and tbselenium with a headless Tor browser to issue requests.

The researchers painstakingly collected per-packet metadata and ground truth data on session start and end times. They created a diverse set of 48 dummy onion services based on plausible content categories from ahmia.fi and simulated realistic user access patterns using a Zipf distribution (α=1.5) to replicate popularity. Clients engaged in concurrent browsing sessions to both onion services and the top 150 Tranco-ranked clearnet websites, with browsing patterns (sequences of requests, stay times) following statistical distributions. Three distinct datasets (OSTrain, OSValidate, OSTest) were collected between April and June 2023, ensuring no overlap in clients, websites, or onion services to prevent data leakage during training and evaluation. This comprehensive setup provided a strong empirical foundation for demonstrating SUMo's effectiveness and efficiency.

Defensive Implications

▶ Watch: Defining the threat model: Colluding ISPs as adversaries (6:00)

The SUMo attack highlights significant vulnerabilities in Tor's anonymity guarantees for onion services, necessitating robust countermeasures. The researchers explored several potential strategies to mitigate SUMo's efficacy:

1. Obfuscation of Tor Flows: Implementing and widely adopting traffic obfuscators like obfs4 could significantly degrade SUMo's precision. These tools are designed to make Tor traffic resemble innocuous traffic, preventing adversaries from easily detecting Tor usage and thus complicating the initial filtering stages of SUMo. Their proven effectiveness against other correlation attacks suggests similar benefits here.

1. Generation of Concurrent Multitab Clearnet Requests (Client-Side): If Tor users actively browse dummy clearnet websites concurrently while accessing an onion service, it would introduce additional "noise" and overlapping webpage requests. This strategy would make SUMo's Target Separation (Step 2) task more difficult, as the classifier would struggle to definitively distinguish between legitimate onion service traffic and intentionally obfuscated clearnet traffic.

1. Generation of Concurrent Onion Service Requests (Server-Side): Onion service providers could actively generate spurious traffic from dummy Tor clients to their own services. By increasing the overall concurrency and volume of traffic exchanged by each onion service, it becomes more challenging for SUMo's correlator to isolate and match specific client-server session flows, particularly during the Pair Concurrent Flows (Step 3) and Sliding Subset Sum (Step 5) stages. This strategy aims to dilute the unique "fingerprint" of individual sessions.

1. Ensuring Diverse Geographic Locations for Client and Onion Service Guard Nodes: A core assumption of flow correlation attacks is that an adversary can monitor both ends of a connection. If mechanisms could be developed to enforce that client and onion service guard nodes are situated in geographically distant and distinct regions, it would become significantly more challenging for a single colluding ISP or ISP coalition to observe both ends of the connection. Exploring novel mechanisms to enforce such geographic diversity could be a promising direction for future Tor improvements.

It's also important to note that while Tor version 0.4.1.5 introduced padding cells during circuit establishment to counter earlier circuit fingerprinting techniques, SUMo's updated filtering phase successfully bypasses this defense. This suggests that more comprehensive and dynamic padding mechanisms throughout the entire Tor session, rather than just during circuit establishment, might be necessary to effectively counter advanced volumetric flow correlation attacks like SUMo.

Key Takeaways

• SUMo is a highly effective and efficient flow correlation attack specifically targeting Tor onion service sessions, capable of deanonymizing endpoint IP addresses.
• A novel distributed pipeline architecture combining machine learning classifiers for filtering and a Sliding Subset Sum algorithm for matching enables SUMo to overcome challenges faced by prior correlation methods on onion service traffic.
• SUMo significantly outperforms state-of-the-art attacks like DeepCoFFEA on onion service traffic, being two orders of magnitude faster and more memory-efficient.
• Longer onion service sessions (over 6 minutes) are highly vulnerable, achieving near-perfect correlation (100% precision and recall) under optimal conditions. Shorter sessions are the primary source of false positives.
• High levels of session concurrency do not prevent SUMo's success, although popular onion services may contribute to more false positives due to their traffic characteristics.
• Effective countermeasures include traffic obfuscation (e.g., obfs4), increasing client-side dummy clearnet browsing, server-side generation of spurious onion service traffic, and promoting geographic diversity of guard nodes.

About the Speaker(s)

Daniela Lopes is the speaker who presented this work at the NDSS Symposium. The provided transcript and metadata do not offer further details about her title, affiliation, or specific background beyond her role as a presenter of this research.