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 consider the problem of a client querying an encrypted binary tree structure, outsourced to an untrusted server. While the server must not learn the contents of the binary tree, we also prevent the client from maliciously crafting a query that traverses the tree out-of-order. That is, the client should not be able to retrieve nodes outside one contiguous path from the root to a leaf. Finally, the server should not learn which path the client accesses, but is guaranteed that the access corresponds to one valid path in the tree. This is an extension of protocols such as structured encryption, where it is only guaranteed that the tree's encrypted data remains hidden from the server.

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.

Abstract TLS, and SSL before it, has long supported the option for clients to authenticate to servers using their own certificates, but this capability has not been widely used. However, with the development of its Push Notification Service, Apple has deployed this technology on millions of devices for the first time. Wachs et al. [42] determined iOS client certificates could be used by passive network adversaries to track individual devices across the internet. Subsequently, Apple has patched their software to fix this vulnerability. We show these countermeasures are not effective by demonstrating three novel active attacks against TLS Client Certificate Authentication that are successful despite the defenses. Additionally, we show these attacks work against all known instances of TLS Client Certificate Authentication, including smart cards like those widely deployed by the Estonian government as part of their Digital ID program. Our attacks include in-path man-in-the-middle versions as well as a more powerful on-path attack that can be carried out without full network control.

Write-Only Oblivious RAM (WoORAM) protocols provide privacy by encrypting the contents of data and also hiding the pattern of write operations over that data. WoORAMs provide better privacy than plain encryption and better performance than more general ORAM schemes (which hide both writing and reading access patterns), and the write-oblivious setting has been applied to important applications of cloud storage synchronization and encrypted hidden volumes. In this paper, we introduce an entirely new technique for Write-Only ORAM, called DetWoORAM. Unlike previous solutions, DetWoORAM uses a deterministic, sequential writing pattern without the need for any "stashing" of blocks in local state when writes fail. Our protocol, while conceptually simple, provides substantial improvement over prior solutions, both asymptotically and experimentally. In particular, under typical settings the DetWoORAM writes only 2 blocks (sequentially) to backend memory for each block written to the device, which is optimal. We have implemented our solution using the BUSE (block device in user-space) module and tested DetWoORAM against both an encryption only baseline of dm-crypt and prior, randomized WoORAM solutions, measuring only a 3x-14x slowdown compared to an encryption-only baseline and around 6x-19x speedup compared to prior work.

Security and privacy are frequently linked for good reason; the more specific information an attacker can gather regarding a person or organization, the more devastating or surgical a targeted attack can be. Armed with this knowledge, many individuals and organizations focus too heavily on protecting privacy while under-emphasizing or entirely neglecting actions which will actually make their systems more secure, a practice known as Security through Obscurity. Such is the case with the Institute of Electrical and Electronics Engineers (IEEE) practice of selling private Organizationally Unique Identifier (OUI) registrations to companies. This feature hides the name and personal information of the company that owns an address block in the IEEE public registry. In this paper, we track the adoption of private address allocation over time and attempt to unmask some of the companies behind this veil. We perform a cursory assessment of collected unencrypted frames transmitted by the devices implementing this practice. We identify that ~86% of observed devices reveal their associated provenance through the content of their unencrypted transmissions, thereby rendering the privacy protection moot. Furthermore, we posit that the practice itself is flawed, inherently drawing unnecessary attention by the public nature of IEEE allocations. Our research reveals the ownership details of private addresses used by critical law enforcement, emergency services, and a variety of physical security systems. The results of our findings have been disclosed with the goal of raising awareness of companies and consumers using products with unsubstantiated security guarantees.

Abstract Media Access Control (MAC) address randomization is a privacy technique whereby mobile devices rotate through random hardware addresses in order to prevent observers from singling out their traffic or physical location from other nearby devices. Adoption of this technology, however, has been sporadic and varied across device manufacturers. In this paper, we present the first wide-scale study of MAC address randomization in the wild, including a detailed breakdown of different randomization techniques by operating system, manufacturer, and model of device. We then identify multiple flaws in these implementations which can be exploited to defeat randomization as performed by existing devices. First, we show that devices commonly make improper use of randomization by sending wireless frames with the true, global address when they should be using a randomized address. We move on to extend the passive identification techniques of Vanhoef et al. to effectively defeat randomization in ~96% of Android phones. Finally, we identify a previously unknown flaw in the way wireless chipsets handle low-level control frames which applies to 100% of devices we tested. This flaw permits an active attack that can be used under certain circumstances to track any existing wireless device.

There have been several attempts recently at using homomorphic encryption to increase the efficiency of Oblivious RAM protocols. One of the most successful has been Onion ORAM, which achieves O(1) communication overhead with polylogarithmic server computation. However, it has two drawbacks. It requires a large block size of B = Ω(log6 N) with large constants. Moreover, while it only needs polylogarithmic computation complexity, that computation consists mostly of expensive homomorphic multiplications. In this work, we address these problems and reduce the required block size to Ω(log4 N). We remove most of the homomorphic multiplications while maintaining O(1) communication complexity. Our idea is to replace their homomorphic eviction routine with a new, much cheaper permute-and-merge eviction which eliminates homomorphic multiplications and maintains the same level of security. In turn, this removes the need for layered encryption that Onion ORAM relies on and reduces both the minimum block size and server computation.

Abstract We revisit the problem of privacy-preserving range search and sort queries on encrypted data in the face of an untrusted data store. Our new protocol RASP has several advantages over existing work. First, RASP strengthens privacy by ensuring forward security: after a query for range [a, b], any new record added to the data store is indistinguishable from random, even if the new record falls within range [a, b]. We are able to accomplish this using only traditional hash and block cipher operations, abstaining from expensive asymmetric cryptography and bilinear pairings. Consequently, RASP is highly practical, even for large database sizes. Additionally, we require only cloud storage and not a computational cloud like related works, which can reduce monetary costs significantly. At the heart of RASP, we develop a new update-oblivious bucket-based data structure. We allow for data to be added to buckets without leaking into which bucket it has been added. As long as a bucket is not explicitly queried, the data store does not learn anything about bucket contents. Furthermore, no information is leaked about data additions following a query. Besides formally proving RASP’s privacy, we also present a practical evaluation of RASP on Amazon Dynamo, demonstrating its efficiency and real world applicability.

With sensitive data being increasingly stored on mobile devices and laptops, hard disk encryption is more important than ever. In particular, being able to plausibly deny that a hard disk contains certain information is a very useful and interesting research goal. However, it has been known for some time that existing ``hidden volume'' solutions, like TrueCrypt, fail in the face of an adversary who is able to observe the contents of a disk on multiple, separate occasions. In this work, we explore more robust constructions for hidden volumes and present HiVE, which is resistant to more powerful adversaries with multiple-snapshot capabilities. In pursuit of this, we propose the first security definitions for hidden volumes, and prove HiVE secure under these definitions. At the core of HiVE, we design a new write-only Oblivious RAM. We show that, when only hiding writes, it is possible to achieve ORAM with optimal O(1) communication complexity and only poly-logarithmic user memory. This is a significant improvement over existing work and an independently interesting result. We go on to show that our write-only ORAM is specially equipped to provide hidden volume functionality with low overhead and significantly increased security. Finally, we implement HiVE as a Linux kernel block device to show both its practicality and usefulness on existing platforms.