I still know you were here: Leveraging probe request templates for identifying Wi-Fi devices at scale

MAC address randomization in Wi-Fi Probe Requests (PRs) is supposed to ensure unlinkability for improving user privacy, but PRs still contain enough information to track or re-identify users without relying on the MAC address. This poses a risk to privacy but may also assist law enforcement in identifying devices present at a crime scene. We examine whether it is possible to separate Wi-Fi devices based on observed PRs with randomized MAC addresses using only the content and structure of these PRs. Previous work has predominantly focused on techniques for device counting using feature reduction as a means to manage data set complexity, and has failed to achieve sufficient accuracy for individual device identification. We propose an approach that leverages templates reflecting a PR's structure to identify its influence based on vendor and device, allowing the use of more complex fingerprinting algorithms that utilize the full set of available features. To that end we examine differences between vendors and devices based on observation length, used information elements, and overlapping Fingerprints (FPs) while ignoring MAC addresses. Using PR templating, we construct a knowledge base of FPs and templates from not only existing public data sets but also a new data set published for future research. Our data set tackles critical challenges in labelling and quality in currently available data sets, and we introduce a streamlined and comprehensible crowdsourcing process including automated measurements to enable other researchers to contribute to our data set. We evaluate our device identification approach on the currently available data and demonstrate that, depending on the data set, between 75 % and 85 % of Wi-Fi devices can be uniquely separated within the anonymity group of devices contributing PRs to the respective data set.