On Monday at the WWDC conference, Apple introduced a cool new feature called “Find My" . Unlike the standard “Find My iPhone” , which relies on the cellular infrastructure and GPS of a lost device, the “Find me” function can even find devices without a SIM. maps and GPS. For example, laptops, or even "stupid" location labels attached to any object (Apple hinted at this only in a broad sense).

The idea is to turn the entire existing network of iPhones into a large-scale crowdsourcing system to track the surrounding objects. Every active iPhone will continuously monitor BLE beacon messages from other devices. When he finds one of these signals, he marks the packet with his GPS coordinates - and sends to Apple servers. It’s very cool for a mess like me who constantly loses things: if I leave my backpack on a tour bus in China in the office, sooner or later someone will stumble upon his signal - and I will instantly know where to find it.

(It’s worth noting that the idea was not invented by Apple. In fact, companies like Tile have been working for a long time. And yes, they should worry about their business).

If you are not impressed with the description above, let me voice the question you should ask: how will this system protect against massive breaches of confidentiality?
')
We list the potential problems:

• If the device constantly emits a BLE signal that uniquely identifies it, everyone has a (one more) way to track you. Marketers are already using the WiFi and Bluetooth MAC addresses for this, and the Find My function creates another tracking channel.
  
• She also declassifies those involved in the process. Now these people will send their current location to Apple (perhaps they are doing this anyway). But now they will have to share this information also with strangers who "lose" their devices. It can end badly.
  
• Fraudsters can also launch active attacks in which they fake the location of your device. Although it seems unlikely, people always surprise.

The good news is that Apple claims that the system really provides reliable privacy through the proper use of cryptography. But, as usual, they refused to give details of the implementation . Andy Greenberg in Wired told the partial technical implementation of the words Apple, which allows you to understand a lot. Unfortunately, this story still leaves huge gaps. I’m going to fill them up with the most likely description of what Apple actually does.

A big caveat: a lot can be completely wrong. I will definitely update the article when Apple tells more.

Some basic problems

To state the script, you need to enter into the picture a few devices. For inspiration, take the 1950s television show Lessi.

The first device we call Timmy is “lost.” Timmy has a BLE radio transmitter, but no GPS or internet connection. Fortunately, he was already mating with a second device called Ruth , who wants to find him. Our main character is Lassie : this is an iPhone of a random (and unaware of it) stranger, who (suppose) has at least a periodic internet connection and reliable GPS. And Lassie is a very good girl. Network devices communicate via Apple's iCloud servers, as shown below:



(Since Timmy and Ruth have to be paired in advance, they probably both belong to the same person. I mentioned that you will need to buy two Apple devices for the system to work? This is fine with Apple).

We are considering a security system, so the first question is: who is the bad guy ? In this situation, the answer is unpleasant: anyone can be a potential intruder . That is why the problem is so interesting.

Anonymity Timmy

The most important aspect of the system is not to allow outsiders to track Timmy , especially when it is not lost. This rules out some fairly obvious solutions, for example, when Timmy's device simply screams: "Hi, my name is Timmy, please call my mom Ruth and let me know that I am lost . " It also eliminates almost any static static identifier, even opaque and similar to random.

The latter requirement is made up of the sad experience of services that abuse static identifiers (for example, your WiFi MAC address ) to track device movement. Apple has been combating this surveillance with mixed success by randomizing identifiers such as MAC addresses. If Apple adds a static tracking ID for “Find My”, all problems will only get worse.

This requirement means that any messages transmitted by Timmy must be opaque. Moreover, the content of these messages should relatively often change to new values ​​that cannot be associated with old ones. One obvious way for a paired device to recognize such messages is to make Timmy and Ruth agree on a long list of random “ aliases ” for Timmy , and let Timmy choose another one.

It really helps. Every time Lassie sees some (unknown) device sending an identifier, she won’t know if it belongs to Timmy : but she can send it to Apple’s servers along with her own GPS location. In case Timmy gets lost, Ruth can ask Apple to find all possible Timmy aliases. In this situation, no one outside of Apple will recognize this list, and even Apple itself will know it only after someone is lost, so this approach prevents most of the tracking options.

A slightly more efficient way to implement this idea is to use a cryptographic function (for example, a MAC or a hash function) to generate a list of aliases from one short “sid”, copies of which are stored by Timmy and Ruth . This is good because it reduces the amount of stored data. But to find Timmy , Ruth still needs to send all the aliases — or Syd — to Apple, which will have to search for each alias in its database.

Hiding the location of Lassie

The described approach with pseudonyms should hide Timmy's personality well from Lassie and even from Apple (up to the point when Ruth starts to look for him). However, there is a big drawback: it does not hide the GPS coordinates of Lassie .

This is bad, at least for several reasons. Every time Lassie discovers a device with a BLE signal, it should send its current location to Apple’s servers (along with the alias that she sees). This means that Lassie constantly tells Apple where she is. Moreover, even if Apple promises not to keep Lassie's identity, the result of all these messages is a huge centralized database that shows all the GPS locations where any Apple device is detected.

Please note that an array of such data in itself gives a lot of information. Yes, device identifiers can be pseudonyms - but this does not make the information useless. For example, if an Apple device broadcasts the same coordinates in the evenings, then it gives the likely address of the person.

The obvious way to prevent Apple from disclosing this data is to encrypt it so that only those who really need to know the location of the device can see the information. If Lassie accepts the message from Timmy , then the only person who really needs to know Lassie’s location is Ruth . To keep this information confidential, Lessie must encrypt her coordinates with the public key of Ruth .

Of course, the question arises: how will Lassie get Ruth's key? The obvious solution for Timmy is to shout out Ruth's public key in every broadcast. But this will create a static ID that again allows you to track down Timmy .

To solve this problem, it is necessary that Ruth has a lot of unattached public keys , so that Timmy can issue different keys with each broadcast. One option is to force Ruth and Timmy to generate many different common key pairs (or to generate many such pairs from a common key). But it is annoying, and Ruth will have to keep many secret keys. And the identifiers mentioned in the previous section can be obtained by hashing each public key.

A slightly better approach (which Apple can use or not) is to randomize keys. This is a feature of some cryptosystems, such as Elgamal : it allows any party to randomize the public key , so it will not be associated with the original. The best part of this feature is that Ruth can use one secret key no matter what randomized version of her public key was used for encryption .



All this leads to the final idea of ​​the protocol. In each broadcast, Timmy broadcasts a new pseudonym and a randomized copy of Ruth ’s public key. When Lassie receives a broadcast, she encrypts her GPS coordinates with a public key and sends an encrypted message to Apple. Ruth can send Timmy aliases to Apple servers, and if Apple finds a match, it can retrieve and decode the GPS coordinates.

Does this solve all the problems?

The unpleasant thing is that there is no perfect solution for many strange border situations. For example, what if Timmy has evil intentions and he wants to force Lassie to reveal his location to Apple? What if Old Smithers tries to kidnap Lassie ?

At some point, the answer to this question comes down to the fact that we have done everything possible: any remaining problems should be moved beyond the framework of the threat model. Sometimes even Lassie knows when to stop.