CELLSHIFT: RTT-Aware Trace Transduction for Real-World Website Fingerprinting

CELLSHIFT: RTT-Aware Trace Transduction for Real-World Website Fingerprinting

Speakers: Rob Jansen

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=tcf-RD6Oxec

Overview

Rob Jansen from the US Naval Research Laboratory presents CellShift, a method for transforming Tor exit-side traffic traces into entry-side traces to improve website fingerprinting attack evaluation using real user data. Website fingerprinting attacks attempt to break Tor anonymity by observing traffic patterns on the entry side of a Tor circuit and predicting which website the user is visiting. The core problem: adversaries need labeled training data, but using synthetic data (automated browser crawls) overestimates attack accuracy because it does not capture real user behavior diversity. CellShift uses round-trip time (RTT) estimates extracted from existing cell metadata to rewrite timestamps, simulating the shift from exit to entry observation point. Using only addition, subtraction, and division, CellShift improves attack accuracy by 1-36 percentage points across 10 classifiers, processes tens of millions of traces per hour (five orders of magnitude faster than simulation-based approaches), and is validated against a genuine dataset of 13 million real Tor user traces from the GTT23 dataset.

Background

▶ Watch: Tor website fingerprinting threat: breaking anonymity via traffic patterns (0:30)

Tor is the leading anonymity network, routing traffic through an entry relay, middle relay, and exit relay to separate user identification from routing. A major threat is website fingerprinting (WF): an adversary at the entry position observes traffic patterns and uses a trained ML classifier to predict the visited website, breaking the client-to-destination unlinkability that Tor provides.

Training a WF classifier requires labeled data -- traffic patterns with known website labels. Two approaches exist. Synthetic data (using Selenium to crawl websites and record patterns) provides labeled entry-side data but oversimplifies the ML task by missing real-world diversity in browser versions, configurations, geolocations, and network conditions. This approach tends to overestimate attack accuracy. Real exit data (running a Tor exit relay to observe genuine user traffic with website labels) captures authentic behavior but produces traces from the wrong observation point. Previous work showed that this entry-exit mismatch reduces classifier performance by 5-93%, with a 17% median reduction.

The GTT23 dataset -- 13 million real Tor user traces collected from exit relays over 13 weeks -- provides an unprecedented opportunity for genuine-data evaluation but suffers from this positional mismatch problem.

Key Findings

▶ Watch: Entry-exit mismatch reduces attack performance by 5-93% (4:00)

Simple math beats network simulation: CellShift uses only addition, subtraction, and division to rewrite cell timestamps. Despite its simplicity, it outperforms the prior Retracer method, which uses full network simulation (simulating the entire Tor network with background traffic) for trace transduction.

1-36 percentage point accuracy improvement: Across 10 different WF classifiers, CellShift improved attack accuracy by 1-7 points when varying the testing set and 8-36 points when varying the training set, compared to using raw exit traces.

Distance reduction validated: Using six different distance functions, CellShift-produced traces were consistently closer to actual entry traces than either raw exit traces or Retracer-produced traces. Retracer actually increased distance from true entry traces in some cases.

Five orders of magnitude faster: The Rust implementation processes tens of millions of traces per hour per CPU, compared to Retracer's simulation-based approach. This enables handling a typical Tor exit relay's circuit load in real time.

Natural world evaluation: In a day-by-day training/testing scenario mimicking real-world adversary operation, CellShift maintained or improved precision while significantly improving recall compared to previous methods.

Technical Deep Dive

▶ Watch: Timestamp rewriting: adding/subtracting per-hop latency (8:00)

A cell trace is a sequence of tuples: timestamp, direction (+1 for client-to-server, -1 for server-to-client), and command (Tor protocol message type). CellShift estimates circuit RTT from two sources within the trace. First, during server connection setup: the time between the exit sending a CONNECTED cell and receiving the first DATA cell from the client provides an RTT estimate. Second, during data relay: Tor's congestion control sends a SENDME cell from the client for every 31 DATA cells received, providing repeated RTT samples throughout the circuit lifetime.

Given the RTT estimates, CellShift divides by 6 (for 3 hops, each contributing to round-trip) to get average per-hop latency. For exit-to-client cells, it adds 2 hops of latency to the exit timestamp. For client-to-exit cells, it subtracts 2 hops of latency. The rewritten cells are resorted by new timestamps to produce the transduced entry trace.

Augmentation extensions split RTT into two components: propagation delay (minimum observed RTT) and congestion (RTTs above the minimum). Congestion values from one trace can be applied to other traces, simulating different relay path conditions and producing training data variations that improve classifier robustness.

The evaluation used a correlated dataset where the researchers ran a client pinned to their own entry and exit relays, providing ground-truth traces from both perspectives. This enabled direct comparison of CellShift's estimated entry traces against actual entry traces using six distance metrics.

Demo / Proof of Concept

▶ Watch: Evaluation on 13 million real Tor traces from GTT23 dataset (12:00)

CellShift was implemented in Rust and is open source. The evaluation covered three phases: a distance evaluation comparing transduced traces to actual entry traces, a synthetic-data WF evaluation across 10 classifiers, and a genuine-data evaluation using the GTT23 dataset (13 million real Tor user traces). The natural-world evaluation simulated an adversary training on day one and testing on subsequent days, demonstrating sustained performance improvement. The implementation processes tens of millions of traces per hour, enabling real-time operation on a typical exit relay.

Defensive Implications

▶ Watch: Rust implementation: tens of millions of traces per hour per CPU (16:00)

Jansen explicitly frames this work as defense-motivated: by understanding the real-world threat of website fingerprinting more accurately, the community can develop and prioritize defenses more effectively. If defenses are only evaluated against synthetic data (which overestimates attack accuracy), defenders may deploy protections that are unnecessary or miss protections that would be effective against real-world attacks. CellShift enables defense evaluation against genuine user data, potentially revealing that the perfect defense may not be necessary -- a "good enough" defense that works against real-world attacks could have meaningful privacy impact without the overhead of theoretical perfection.

The open-source Rust implementation and the publicly available GTT23 dataset enable the broader research community to evaluate both attacks and defenses against realistic data, raising the quality bar for website fingerprinting research.

Key Takeaways

• CellShift transforms exit-side Tor traces to entry-side using only RTT-based timestamp rewriting (addition, subtraction, division)
• Improves WF attack accuracy by 1-36 percentage points across 10 classifiers compared to using raw exit traces
• Five orders of magnitude faster than simulation-based transduction, enabling real-time processing of exit relay traffic
• Validated on 13 million genuine Tor user traces from the GTT23 dataset -- not synthetic data
• Open-source Rust implementation and public dataset enable reproducible defense evaluation
• Ultimately defense-motivated: better attack understanding leads to better-informed, more efficient privacy protections

About the Speaker(s)

Rob Jansen is a researcher at the US Naval Research Laboratory specializing in Tor network security, privacy, and performance. His work focuses on understanding website fingerprinting attacks to inform defense development, with the explicit goal of promoting privacy and security for Tor users. He is the creator of the Shadow network simulator and has made significant contributions to Tor performance measurement and simulation.