Fully Encrypted Protocols (FEPs) have arisen in practice as a technique to avoid network censorship. Such protocols are designed to produce messages that appear completely random. This design hides communications metadata, such as version and length fields, and makes it difficult to even determine what protocol is being used. Moreover, these protocols frequently support padding to hide the length of protocol fields and the contained message. These techniques have relevance well beyond censorship circumvention, as protecting protocol metadata has security and privacy benefits for all Internet communications. The security of FEP designs depends on cryptographic assumptions, but neither security definitions nor proofs exist for them. We provide novel security definitions that capture the metadata-protection goals of FEPs. Our definitions are given in both the datastream and datagram settings, which model the ubiquitous TCP and UDP interfaces available to protocol designers. We prove relations among these new notions and existing security definitions. We further present new FEP constructions and prove their security. Finally, we survey existing FEP candidates and characterize the extent to which they satisfy FEP security. We identify novel ways in which these protocols are identifiable, including their responses to the introduction of data errors and the sizes of their smallest protocol messages.

In 2020, Apple introduced the Find My protocol, which allows owners to crowdsource the location of their lost Apple devices even when the lost device has no active internet connection (e.g., Wi-Fi, Cellular). The Find My protocol is the basis for Apple's AirTag tracking tokens which were released later in 2021. In order to prevent malicious use of these tokens, Apple also implemented ``item safety alerts'' which can warn a person if they are being tracked by an AirTag without their knowledge. However, researchers have recently identified several shortcomings with these alerts that allow modified AirTags to track unsuspecting victims indefinitely without being detected. Making matters worse, while recognizing the observed malicious use of AirTags, news reports, Apple's press releases, and their intended anti-tracking improvements to the protocol do not consider the potential surreptitious use of the Find My network by custom built AirTag clones. In this work, we present an improved Find My protocol which effectively limits the capabilities of malicious AirTags and guarantees that they can be detected while tracking. We accomplish this by adding additional cryptographic verification into the protocol, which restricts tags to only using a bounded set of keys while tracking. In order to maintain - and exceed - the privacy guarantees of the current Find My protocol, we make use of specialized partial blind signatures. To demonstrate the practicality of this protocol, we implement it end-to-end using a programmable device with the same SoC (nRF52832) as in current AirTags. We also benchmark the cryptographic operations of our protocol and show that they require only modest overhead during the initial pairing procedure.

We introduce cryptographic protocols for securely and efficiently computing the cardinality of set union and set intersection. Our private set-cardinality protocols ( PSC ) are designed for the setting in which a large set of parties in a distributed system makes observations, and a small set of parties with more resources and higher reliability aggregates the observations. PSC allows for secure and useful statistics gathering in privacy-preserving distributed systems. For example, it allows operators of anonymity networks such as Tor to securely answer the questions: How many unique users are using the network? and How many hidden services are being accessed? We prove the correctness and security of PSC in the Universal Composability framework against an active adversary that compromises all but one of the aggregating parties. Although successful output cannot be guaranteed in this setting, PSC either succeeds or terminates with an abort, and we furthermore make the adversary accountable for causing an abort by blaming at least one malicious party. We also show that PSC prevents adaptive corruption of the data parties from revealing past observations, which prevents them from being victims of targeted compromise, and we ensure safe measurements by making outputs differentially private. We present a proof-of-concept implementation of PSC and use it to demonstrate that PSC operates with low computational overhead and reasonable bandwidth. It can count tens of thousands of unique observations from tens to hundreds of data-collecting parties while completing within hours. PSC is thus suitable for daily measurements in a distributed system.

Abstract Mobile device manufacturers and operating system developers increasingly deploy MAC address randomization to protect user privacy and prevent adversaries from tracking persistent hardware identifiers. Early MAC address randomization implementations suffered from logic bugs and information leakages that defeated the privacy benefits realized by using temporary, random addresses, allowing devices and users to be tracked in the wild. Recent work either assumes these implementation flaws continue to exist in modern MAC address randomization implementations, or considers only dated software or small numbers of devices. In this work, we revisit MAC address randomization by performing a cross-sectional study of 160 models of mobile phones, including modern devices released subsequent to previous studies. We tested each of these phones in a lab setting to determine whether it uses randomization, under what conditions it randomizes its MAC address, and whether it mitigates known tracking vulnerabilities. Our results show that, although very new phones with updated operating systems generally provide a high degree of privacy to their users, there are still many phones in wide use today that do not effectively prevent tracking.

Abstract We investigate Apple’s Bluetooth Low Energy (BLE) Continuity protocol, designed to support interoperability and communication between iOS and macOS devices, and show that the price for this seamless experience is leakage of identifying information and behavioral data to passive adversaries. First, we reverse engineer numerous Continuity protocol message types and identify data fields that are transmitted unencrypted. We show that Continuity messages are broadcast over BLE in response to actions such as locking and unlocking a device’s screen, copying and pasting information, making and accepting phone calls, and tapping the screen while it is unlocked. Laboratory experiments reveal a significant flaw in the most recent versions of macOS that defeats BLE Media Access Control (MAC) address randomization entirely by causing the public MAC address to be broadcast. We demonstrate that the format and content of Continuity messages can be used to fingerprint the type and Operating System (OS) version of a device, as well as behaviorally profile users. Finally, we show that predictable sequence numbers in these frames can allow an adversary to track Apple devices across space and time, defeating existing anti-tracking techniques such as MAC address randomization.

This paper introduces a cryptographic protocol for efficiently aggregating a count of unique items across a set of data parties privately - that is, without exposing any information other than the count. Our protocol allows for more secure and useful statistics gathering in privacy-preserving distributed systems such as anonymity networks; for example, it allows operators of anonymity networks such as Tor to securely answer the questions: how many unique users are using the distributed service? and how many hidden services are being accessed?. We formally prove the correctness and security of our protocol in the Universal Composability framework against an active adversary that compromises all but one of the aggregation parties. We also show that the protocol provides security against adaptive corruption of the data parties, which prevents them from being victims of targeted compromise. To ensure safe measurements, we also show how the output can satisfy differential privacy.