June 6, 2019 at 12:18How will Apple (privately) find offline your lost device?
- Transfer
On Monday at Apple’s WWDC, Apple introduced a cool new feature called “Find My . ” Unlike the standard “Find My iPhone,” which relies on the cellular and GPS infrastructure of a lost device, the Find Me feature can even find devices without a SIM. -cards and GPS: for example, laptops, or even “dumb” location tags attached to any item (Apple hinted at it only in a broad sense).
The idea is to turn the entire existing network of iPhones into a large-scale crowdsourcing system for tracking surrounding objects. Every active iPhone will constantly monitor BLE beacon messages coming from other devices. When he finds one of these signals, he marks the packet with his GPS coordinates and sends it to Apple servers. This is great for bewilders like me, who constantly lose things: if I leave my backpackon a tourist bus in China in the office, sooner or later someone will stumble upon his signal - and I will instantly find out where to find him.
(It’s worth noting that it wasn’t Apple who came up with the idea. In fact, companies like Tile have been around for quite some time. And yes, they should worry about their business).
If you are not impressed with the description above, let me raise a question that you should ask: how will this system protect against massive privacy violations?
We list potential problems:
The good news is that Apple claims that the system does provide strong privacy through the proper use of cryptography. But, as usual, they refused to provide implementation details . Andy Greenberg at Wired described a partial technical implementation from Apple, which allows a lot to be understood. Unfortunately, this story still leaves enormous gaps. It is I who I am going to fill in, offering the most likely description of what Apple is actually doing.
A big caveat: a lot can be completely wrong. I will definitely update the article when Apple tells more.
To outline the scenario, you need to introduce several devices into the picture. For inspiration, take the 1950s television series Lassie.
The first device we'll call Timmy is “lost.” At Timmy have a radio transmitter BLE, but there is no GPS or internet connection. Fortunately, he was already paired with a second device called Ruth , who wanted to find him. Our main character is Lassie : this is an iPhone of a random (and unaware) stranger who (suppose) has at least a periodic Internet connection and reliable GPS. And Lassie is a very good girl. Network devices communicate through Apple's iCloud servers, as shown below:
(Since Timmy and Ruthshould be paired in advance, probably both belong to the same person. Did I mention 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 could be a potential attacker . That is why the problem is so interesting.
The most important aspect of the system is that you must not allow outsiders to keep track of Timmy , especially when he is not lost. This eliminates some fairly obvious decisions, for example, when Timmy’s device simply shouts: “Hi, my name is Timmy, please call my mother Ruth and let me know that I’m lost . ” It also eliminates virtually any immutable static identifier, even opaque and random.
The last requirement is made up of the sad experience of services that abuse static identifiers (for example, your WiFi MAC address ) to track the movement of devices. Apple with mixed successfights this snooping by randomizing identifiers such as MAC addresses. If Apple adds a static tracking identifier for “Find My,” all problems will only get worse.
This requirement means that any messages sent by Timmy must be opaque. Moreover, the content of these messages should change relatively often to new values that cannot be associated with old ones. One obvious way for a paired device to recognize such messages is to get Timmy and Ruth to agree on a long list of random “ aliases ” for Timmy , and let Timmy choose a different one each time.
It really helps. Every time whenLassie sees some (unknown) device transmitting the identifier, she will not know if it belongs to Timmy : but she can send it to Apple servers along with her own GPS location. In the event that Timmy gets lost, Ruth may 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 recognize it only after someone is lost, so this approach prevents most 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 data stored. But in order to find Timmy , Ruth still needs to send all the nicknames - or seed - to Apple, which will have to look for every nickname in its database.
The described approach with pseudonyms should well hide Timmy’s identity from Lassie and even from Apple (until the moment when Ruth starts looking for him). However, there is a big drawback: it does not hide the GPS coordinates of Lassie . This is bad for at least a few reasons. Each time Lassie discovers a device with a BLE signal, she must send her current location to Apple servers (along with the alias she sees). This means that Lassie constantly tells Apple where she is. And what's more, 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 found .
Please note that the array of such data alone produces a lot of information. Yes, device identifiers can be aliases - but this does not make the information useless. For example, if some Apple device broadcasts the same coordinates in the evenings, then this gives the probable address of the person.
An 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 see the information . If Lassie receives a message from Timmy, then the only person who really needs to know Lassie's location is Ruth . To keep this information secret, Lassie must encrypt her coordinates with Ruth's public key .
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 each of his broadcasts. But this will create a static identifier that again allows Timmy to be tracked .
To solve this problem, Ruth must have many untethered public keys , so that Timmycould give out different keys with each broadcast. One option is to get Ruth and Timmy to generate many different common key pairs (or to generate many such pairs from a common sid). But this 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) involves key randomization . This is a feature of some cryptosystems such as Elgamal : it allows either side to randomize the public keyso that it will not be associated with the original. The best part of this feature is that Ruth can use one secret key no matter which randomized version of her public key was used for encryption .
All this leads to the final idea of the protocol. In each broadcast, Timmy transmits a new alias and a randomized copy of Ruth 's public key . When Lassie receives the broadcast, she encrypts her GPS coordinates with the public key and sends an encrypted message to Apple. Ruth can send Timmy aliases to Apple servers, and if Apple finds a match, she can receive and decrypt GPS coordinates.
The unpleasant thing is that there is no ideal solution for many strange border situations. For example, what if Timmy has evil intentions and wants to make Lassie reveal her Apple location? What if Old Smithers tries to kidnap Lassie ?
At some point, the answer to this question comes down to the fact that we did everything possible: any remaining problems should be moved beyond the threat model. Sometimes even Lassie knows when to stop.
The idea is to turn the entire existing network of iPhones into a large-scale crowdsourcing system for tracking surrounding objects. Every active iPhone will constantly monitor BLE beacon messages coming from other devices. When he finds one of these signals, he marks the packet with his GPS coordinates and sends it to Apple servers. This is great for bewilders like me, who constantly lose things: if I leave my backpack
(It’s worth noting that it wasn’t Apple who came up with the idea. In fact, companies like Tile have been around for quite some time. And yes, they should worry about their business).
If you are not impressed with the description above, let me raise a question that you should ask: how will this system protect against massive privacy violations?
We list potential problems:
- If the device constantly emits a BLE signal that uniquely identifies it, everyone has got (another) way to track you. Marketers already use 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 (maybe they already do that). 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 this seems unlikely, people are always surprised.
The good news is that Apple claims that the system does provide strong privacy through the proper use of cryptography. But, as usual, they refused to provide implementation details . Andy Greenberg at Wired described a partial technical implementation from Apple, which allows a lot to be understood. Unfortunately, this story still leaves enormous gaps. It is I who I am going to fill in, offering the most likely description of what Apple is actually doing.
A big caveat: a lot can be completely wrong. I will definitely update the article when Apple tells more.
Some major issues
To outline the scenario, you need to introduce several devices into the picture. For inspiration, take the 1950s television series Lassie.
The first device we'll call Timmy is “lost.” At Timmy have a radio transmitter BLE, but there is no GPS or internet connection. Fortunately, he was already paired with a second device called Ruth , who wanted to find him. Our main character is Lassie : this is an iPhone of a random (and unaware) stranger who (suppose) has at least a periodic Internet connection and reliable GPS. And Lassie is a very good girl. Network devices communicate through Apple's iCloud servers, as shown below:
(Since Timmy and Ruthshould be paired in advance, probably both belong to the same person. Did I mention 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 could be a potential attacker . That is why the problem is so interesting.
Timmy Anonymity
The most important aspect of the system is that you must not allow outsiders to keep track of Timmy , especially when he is not lost. This eliminates some fairly obvious decisions, for example, when Timmy’s device simply shouts: “Hi, my name is Timmy, please call my mother Ruth and let me know that I’m lost . ” It also eliminates virtually any immutable static identifier, even opaque and random.
The last requirement is made up of the sad experience of services that abuse static identifiers (for example, your WiFi MAC address ) to track the movement of devices. Apple with mixed successfights this snooping by randomizing identifiers such as MAC addresses. If Apple adds a static tracking identifier for “Find My,” all problems will only get worse.
This requirement means that any messages sent by Timmy must be opaque. Moreover, the content of these messages should change relatively often to new values that cannot be associated with old ones. One obvious way for a paired device to recognize such messages is to get Timmy and Ruth to agree on a long list of random “ aliases ” for Timmy , and let Timmy choose a different one each time.
It really helps. Every time whenLassie sees some (unknown) device transmitting the identifier, she will not know if it belongs to Timmy : but she can send it to Apple servers along with her own GPS location. In the event that Timmy gets lost, Ruth may 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 recognize it only after someone is lost, so this approach prevents most 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 data stored. But in order to find Timmy , Ruth still needs to send all the nicknames - or seed - to Apple, which will have to look for every nickname in its database.
Hiding the location of Lassie
The described approach with pseudonyms should well hide Timmy’s identity from Lassie and even from Apple (until the moment when Ruth starts looking for him). However, there is a big drawback: it does not hide the GPS coordinates of Lassie . This is bad for at least a few reasons. Each time Lassie discovers a device with a BLE signal, she must send her current location to Apple servers (along with the alias she sees). This means that Lassie constantly tells Apple where she is. And what's more, 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 found .
Please note that the array of such data alone produces a lot of information. Yes, device identifiers can be aliases - but this does not make the information useless. For example, if some Apple device broadcasts the same coordinates in the evenings, then this gives the probable address of the person.
An 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 see the information . If Lassie receives a message from Timmy, then the only person who really needs to know Lassie's location is Ruth . To keep this information secret, Lassie must encrypt her coordinates with Ruth's public key .
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 each of his broadcasts. But this will create a static identifier that again allows Timmy to be tracked .
To solve this problem, Ruth must have many untethered public keys , so that Timmycould give out different keys with each broadcast. One option is to get Ruth and Timmy to generate many different common key pairs (or to generate many such pairs from a common sid). But this 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) involves key randomization . This is a feature of some cryptosystems such as Elgamal : it allows either side to randomize the public keyso that it will not be associated with the original. The best part of this feature is that Ruth can use one secret key no matter which randomized version of her public key was used for encryption .
All this leads to the final idea of the protocol. In each broadcast, Timmy transmits a new alias and a randomized copy of Ruth 's public key . When Lassie receives the broadcast, she encrypts her GPS coordinates with the public key and sends an encrypted message to Apple. Ruth can send Timmy aliases to Apple servers, and if Apple finds a match, she can receive and decrypt GPS coordinates.
Does it solve all the problems?
The unpleasant thing is that there is no ideal solution for many strange border situations. For example, what if Timmy has evil intentions and wants to make Lassie reveal her Apple location? What if Old Smithers tries to kidnap Lassie ?
At some point, the answer to this question comes down to the fact that we did everything possible: any remaining problems should be moved beyond the threat model. Sometimes even Lassie knows when to stop.