Back

TL;DR thread. When Apple launched their “Find My” system for lost devices in 2019, they designed a clever solution to keep bad actors (including Apple) from tracking users. This works by making devices change their broadcast identifier every 15 minutes. https://blog.cryptographyengineering.com/2019/06/05/how-does-apple-privately-find-your-offline-devices/

Two years later, Apple introduced the AirTag. At this point they noticed a problem: people were using location trackers to stalk victims, by placing them on victims’ possessions or cars. This led to some horrific outcomes. https://arstechnica.com/tech-policy/2023/10/apple-airtags-triggered-explosion-of-stalking-reports-nationwide-lawsuit-says/

To fight this, Apple introduced a feature that allows your phone to detect if someone else’s AirTag is “moving with you.”

But this posed a conundrum: if AirTags routinely change their identifier to preserve privacy, how can your phone detect that the same AirTag is stalking you?

The answer, it turns out, is that Apple dialed back the privacy guarantees of their protocol. When an AirTag is near its owner’s phone it changes its identifier every 15 minutes. When it’s away from the owner phone, it changes its identifier only once every 24 hours.

This makes tracking AirTags much easier, since AirTag holders now carry a device with a relatively long-lived identifier, which can be tracked by any mobile device with a Bluetooth connection. If you carry it around with you, chances are you can be traced back to your house.

(Apple and Google are working on a joint IETF standard that will mandate this lower level of privacy. Here’s the relevant section.) https://datatracker.ietf.org/doc/draft-detecting-unwanted-location-trackers/

So the question we set out to investigate is: can you have devices that change their identifiers constantly (every 15 minutes or even faster) to ensure privacy against unwanted tracking, but still allow victims to detect stalker tags?

This is a tough problem, because the goal of a “tracking adversary” is almost the same as the goal of a potential stalking victim. They both want to link together the broadcasts of a single AirTag. Only one is a “bad guy” and one is a “good guy”.

The solution we developed uses “secret sharing.” Each device has a long-lived secret, but instead of broadcasting that, it broadcasts a “share” of its secret every few minutes. If any receiver obtains a sufficient number of shares, they can put them together and detect the tag.

The neat thing about secret sharing is that, to anyone who receives too few shares — ie, you don’t spend hours standing next to them with your tag — the shares look like random numbers. A stalking victim, by definition, gets lots of shares. People tracking you likely will not.

While this idea seems simple, the challenge is that there are a lot of AirTags in the world! The broadcasts of unrelated “bystander” AirTags can’t be distinguished from the broadcasts of a stalker. (Indeed if you could distinguish them easily, it would allow tracking.)

Hence what we need is an algorithm that can recover a secret from its shares, in the presence of many unrelated “noise” shares sent by other devices with different secrets. This could involve hundreds of legitimate shares and thousands of unrelated (innocent) shares.

Also, this algorithm has to run on your smartphone, since we can’t trust Apple to do the processing (since sending all this data to their servers would give them enough information to track innocent AirTag users.)

This turns one problem (secret sharing) into a related problem (error correction coding.) The legitimate shares are like pieces of true signal, and the unrelated AirTag broadcasts can be viewed as “noise.” A number of very clever algorithms exist solve this problem… in theory.

The problem with theory is that it’s, well, theoretical. Many of the brilliant coding algorithms in the literature have not been implemented. When you start to implement them *as written*, for the large numbers of shares we need, they quickly overwhelm the capabilities of a smartphone.

Fortunately there is a parallel literature that uses very efficient lattice reduction methods to achieve these goals. With some customization, we were able to make these algorithms run in the RAM/compute requirements of a smartphone.

There is a lot more to this, obviously. For a full description of the work, here is our pre-print: https://eprint.iacr.org/2023/1332.pdf

Even if this is not the solution Apple (and Tile and Samsung) eventually adopt, I hope they will consider improving the privacy guarantees of these devices. // fin