Abstract
Network flow fingerprinting can be used to de-anonymize communications on anonymity systems such as Tor by linking the ingress and egress segments of anonymized connections. Assume Alice and Bob have access to the input and the output links of an anonymous network, respectively, and they wish to collaboratively reveal the connections between the input and the output links without being detected by Willie who protects the network. Alice generates a codebook of fingerprints, where each fingerprint corresponds to a unique sequence of inter-packet delays and shares it only with Bob. For each input flow, she selects a fingerprint from the codebook and embeds it in the flow, i.e., changes the packet timings of the flow to follow the packet timings suggested by the fingerprint, and Bob extracts the fingerprints from the output flows. We model the network as parallel $M/M/1$ queues where each queue is shared by a flow from Alice to Bob and other flows independent of the flow from Alice to Bob. The timings of the flows are governed by independent Poisson point processes. Assuming all input flows have equal rates and that Bob observes only flows with fingerprints, we first present two scenarios: 1) Alice fingerprints all the flows; 2) Alice fingerprints a subset of the flows, unknown to Willie. Then, we extend the construction and analysis to the case where flow rates are arbitrary as well as the case where not all the flows that Bob observes have a fingerprint. For each scenario, we derive the number of flows that Alice can fingerprint and Bob can trace by fingerprinting.
Introduction
Anonymity systems like Tor protect users by relaying traffic through multiple nodes to hide the connection between an ingress point and an egress point. However, an adversary controlling both ends can link these segments through "flow fingerprinting"—subtly altering packet timings at the entry to be recognized at the exit. The primary constraint is the presence of a "Warden" (Willie), who monitors the network for such interference. This paper establishes the fundamental limits of invisible fingerprinting, where manipulated traffic remains statistically indistinguishable from normal traffic.
System Model and Methodology
The network is modeled as a series of parallel $M/M/1$ queues. To maintain invisibility while overcoming the "causality constraint" (the inability to send a packet before it arrives), Alice employs a two-phase strategy:
- Invisible Buffering: Alice slightly slows down the flow (e.g., from rate $\lambda$ to $\lambda - \Delta$) to build a packet backlog. This ensures she has packets ready to send exactly when the fingerprint timing requires it.
- Fingerprinting Phase: Alice releases packets according to a secret codebook of inter-packet delays shared only with Bob.
The authors use Information Theory, specifically Kullback–Leibler (KL) divergence, to quantify invisibility. If the statistical deviation is sufficiently small, Willie's detection capability is limited to random guessing.
Key Insights and Results
A critical finding is the "Power of Uncertainty." In scenarios where Alice fingerprints only an unknown subset of flows, the number of traceable flows increases significantly because the Warden must monitor a vast number of flows to detect a minor perturbation in a few. This makes the detection task exponentially harder for Willie.
The research derives scaling laws showing that Alice and Bob can reliably trace $m = O(T / \log T)$ flows within a time interval $T$. Simulations using synthetic Poisson processes and Weibull distributions (to test robustness against non-exponential service times) confirm these limits. Results show that when Alice operates within the derived limits, the Warden's detection probability remains near the diagonal of an ROC curve, indicating successful invisibility.
Conclusion and Future Work
While the $M/M/1$ model provides a rigorous theoretical foundation, real-world networks introduce complexities like packet loss and re-ordering. Future research aims to extend these limits to more complex topologies, such as tandem queues, and non-Poisson arrival patterns ($G/M/1$ queues). This work provides the first mathematical framework for understanding the capacity of timing channels in anonymous networks.
Summary updated