Offline finding (OF) protocols---such as Apple's Find My, Google's Find Hub, Samsung’s SmartThingsFind, and Tile---enable hundreds of millions of users to track their belongings via Bluetooth-based tracker tags. However, their scale and tracking capabilities give rise to privacy risks for tag owners and bystanders, as well as safety risks for victims of tag-facilitated stalking. In response, academics and practitioners have suggested cryptographic and non-cryptographic mitigations to improve privacy and anti-stalking protections, working to navigate complex and subtle tensions between these goals. The result is a large landscape of privacy goals, threat models, protocol designs, implementations, and analyses. In this work, we systematize the OF protocol landscape. We gather and analyze a corpus of 49 research papers and OF protocol technical specifications, and use it to develop a taxonomy capturing the functionality, security, and privacy goals of OF protocols. We use the taxonomy to guide a focused assessment of the four major OF deployments along with six academic constructions, comparing design choices, consolidating known attacks, and analyzing the designs' trade-offs between privacy, security, abusability, and efficiency. We provide a simple OF protocol that achieves most security goals, and which clarifies the essential cryptographic components underlying OF protocols. We also provide a survey of physical layer attacks and usability issues that undermine protections in practice. Finally, we discuss open problems and potential research directions towards secure, interoperable, and abuse-resistant OF systems.

The MD transform that underlies the MD and SHA families iterates a compression function h to get a hash function H. The question we ask is, what property X of h guarantees collision resistance (CR) of H? The classical answer is that X itself be CR. We show that weaker conditions X, in particular forms of what we call constrained-CR, suffice. This reduces demands on compression functions, to the benefit of security, and also, forensically, explains why collision-finding attacks on compression functions have not, historically, lead to immediate breaks of the corresponding hash functions. We obtain our results via a definitional framework called RS security, and a parameterized treatment of MD, that also serve to unify prior work and variants of the transform.

We present new algorithm-substitution attacks (ASAs) on symmetric encryption that improve over prior ones in two ways. First, while prior attacks only broke a sub-class of randomized schemes having a property called coin injectivity, our attacks break ALL randomized schemes. Second, while prior attacks are stateful, ours are stateless, achieving a notion of strong undetectability that we formalize. Together this shows that ASAs are an even more dangerous and powerful mass surveillance method than previously thought. Our work serves to increase awareness about what is possible with ASAs and to spur the search for deterrents and counter-measures.