CrossLink: Breaking Location Privacy by Linking Device Identifiers Across Protocols

An uncertainty-aware tracing algorithm that stitches device identifiers across LTE, WiFi, and BLE, revealing that per-protocol privacy defenses do not compose.

Aneet Kumar Dutta; Mihirraj Dixit; Kevin Gni; Wouter Lueks; Mridula Singh· 2026· DOI 10.48550/arXiv.2609.09963

The core problem

Smartphones continuously transmit temporary identifiers over multiple wireless protocols—LTE, WiFi, and BLE—to enable connectivity and services. Privacy defenses, such as MAC address randomization and temporary subscriber identifiers, aim to prevent long-term tracking by rotating these identifiers frequently. However, existing analyses typically evaluate each protocol in isolation, implicitly assuming that protections compose across protocols. This paper challenges that assumption by introducing CrossLink, an uncertainty-aware tracing algorithm that links identifiers across time, space, and protocols. The authors show that even when each protocol leaks only temporary identifiers and the adversary is fully passive, unsynchronized identifier rotations create sufficient cross-protocol evidence to stitch together device traces. This work underscores the need for a joint privacy analysis across protocols, as per-protocol defenses may fail to protect location privacy in practice.

Under large-scale mobility simulation, CrossLink reconstructs full traces for 83% of users, compared to only 22% for the best single-protocol baseline. This stark difference demonstrates the power of cross-protocol linking. In controlled lab experiments, CrossLink also successfully linked identifiers across protocols, confirming the feasibility of the attack in real-world settings. The authors further show that CrossLink remains effective under partial coverage. Strategically placed sniffers near LTE handover regions, mobile sniffers, and limited high-coverage subregions retain sufficient cross-protocol evidence to bridge observation gaps, achieving substantially higher linkability than random deployments. For instance, with only 10% of the area covered by sniffers, CrossLink still reconstructs traces for over 50% of users when sniffers are placed near handover regions, whereas random placement yields less than 20%. These results highlight that even sparse but well-placed observation points can enable large-scale tracking.

Smartphones continuously transmit temporary identifiers over multiple wireless protocols—LTE, WiFi, and BLE—to enable connectivity and services. Privacy defenses, such as MAC address randomization and temporary subscriber identifiers, aim to prevent long-term tracking by rotating these identifiers frequently. However, existing analyses typically evaluate each protocol in isolation, implicitly assuming that protections compose across protocols. This paper challenges that assumption by introducing CrossLink, an uncertainty-aware tracing algorithm that links identifiers across time, space, and protocols. The authors show that even when each protocol leaks only temporary identifiers and the adversary is fully passive, unsynchronized identifier rotations create sufficient cross-protocol evidence to stitch together device traces. This work underscores the need for a joint privacy analysis across protocols, as per-protocol defenses may fail to protect location privacy in practice.

CrossLink operates by modeling the uncertainty in location and mobility and linking identifiers across protocols. The algorithm leverages the fact that identifier rotations are unsynchronized across protocols, meaning that at any given time, a device may have different temporary identifiers in each protocol. By correlating observations across protocols and over time, CrossLink can associate identifiers belonging to the same device. The authors evaluate CrossLink using two approaches: (1) controlled lab experiments with commodity devices, and (2) large-scale mobility simulation. In the lab, they collect real traces of LTE, WiFi, and BLE identifiers from smartphones moving in a controlled environment. For the simulation, they generate synthetic mobility traces for a large population and simulate identifier rotations and observations by sniffers. The algorithm's performance is measured by the percentage of users whose full traces are reconstructed. The authors also test robustness under partial coverage scenarios, including strategically placed sniffers near LTE handover regions, mobile sniffers, and limited high-coverage subregions.

The findings of this paper have significant implications for location privacy. They show that per-protocol privacy defenses do not compose; an adversary can link identifiers across protocols to reconstruct full device traces. This is particularly concerning because the adversary is fully passive—they only observe the wireless medium and do not inject any signals. The unsynchronized nature of identifier rotations, which is inherent to independent protocol implementations, creates a side channel that CrossLink exploits. The authors argue that location privacy must be analyzed jointly across protocols, and defenses should be designed with cross-protocol linking in mind. Potential countermeasures include synchronizing identifier rotations across protocols, adding artificial noise to observations, or using mix networks. However, each has trade-offs in terms of performance and complexity. The paper also demonstrates that partial coverage is sufficient for effective linking, meaning that even limited deployment of sniffers can compromise privacy. This raises questions about the feasibility of achieving strong location privacy in practice. To illustrate the cross-protocol linking process, consider the following Mermaid diagram: This diagram shows how identifiers from different protocols observed at different times can be linked to reconstruct a device's path.

CS practitioners and researchers

Opening member content…