Toward a Secure Crowdsourced Location Tracking System

Chinmay Garg
University of California, Santa Barbara

Aravind Machiry
Purdue University

Andrea Continella
University of Twente

Christopher Kruegel
University of California, Santa Barbara

Giovanni Vigna
University of California, Santa Barbara

Low-energy Bluetooth devices have become ubiquitous and widely used for different applications.
Among these, Bluetooth trackers are becoming popular as they allow users to track the location of their physical objects.
To do so, Bluetooth trackers are often built-in within other commercial products connected to a larger crowdsourced tracking system.
Such a system, however, can pose a threat to the security and privacy of the users, for instance, by revealing the location of a user's valuable object.
In this paper, we introduce a set of security properties and investigate the state of commercial crowdsourced tracking systems, which present common design flaws that make them insecure.
Leveraging the results of our investigation, we propose a new design for a secure crowdsourced tracking system (), which allows devices to leverage the benefits of the crowdsourced model without sacrificing security and privacy.
Our preliminary evaluation shows that is a practical, secure, and effective crowdsourced tracking solution.

§ INTRODUCTION

Tracking devices have become very common for a wide range of applications and use cases.
People use tracking devices to monitor trucking fleet movements, commercial and defense vehicles, monitor their pets and keep track of the location of their valuables in case they are stolen or lost.
While trackers can rely on different technologies, such as radio waves, GPS, and WiFi, Bluetooth Low-Energy (BLE) trackers have become the main choice for consumer-targeted trackers <cit.>, and they are currently used by millions of users.
For instance, the popular TrackR app has more than 1,000,000 downloads from the Google Play Store <cit.>.

In practice, BLE trackers consist of small and cheap devices that can be attached to key rings, luggage, wallets, or any other personal belonging that a user wishes to track.
Once activated, they work by communicating with a mobile app installed on the users' smartphone. The app allows the users to interact with the trackers (e.g., make it ring) and acts as a medium of communication to “connect” the BLE trackers to the Internet.
In fact, the “killer feature” of such devices is the ability for users to remotely query for the location of their valuables.
To do so, BLE trackers are embedded into a more complex ecosystem, called crowdsourced location tracking system.
In a crowdsourced model, users can track the location of their physical devices by leveraging information collected and produced by other users in the network.
In practice, crowdsourced tracking systems rely on all their users, and on their smartphones' GPS, to obtain information about the location of their nearby BLE trackers.
This allows the owner of a BLE tracker to know the location of their valuable (almost) in real-time, even when they are not in proximity of the tracker.
At the same time, the crowdsourced model allows vendors to drastically reduce the cost of their trackers, as they do not need to embed GPS capabilities.

However, due to the nature of the distributed crowdsourced model, which utilizes smartphones for location updates, crowdsourced location tracking systems raise questions regarding the security and privacy of their protocols.
Such questions come naturally since attackers could potentially abuse the systems to perform illicit operations, , stealing or inferring the location of a valuable object.
Indeed, a recent study showed that different tracking systems led to various privacy issues <cit.>.

In this work, we perform a detailed, principled, and comprehensive security analysis of the existing crowdsourced location tracking systems.

We first formalize a set of security properties that every crowdsourced tracking system should fulfill, together with the conditions that must be satisfied to guarantee such properties.
We then study the most popular, commercial, crowdsourced tracking systems, identifying major systematic flaws that violate our security properties and, therefore, allow attackers to obtain unauthorized access to tracked devices.
We responsibly disclosed our findings to the affected vendors.

Finally, inspired by our security properties, we design the protocol of a secure crowdsourced tracking system (), which allows users to leverage all the benefits of the crowdsourced model without compromising their security and privacy.
Our design guarantees reliable (i.e., unspoofable) and anonymous location information, and provides end-to-end encryption, where only the owner of a BLE tracker can access its location.
As a consequence, our design protects the location information even from server-side data breaches <cit.>.

In summary, we make the following contributions:

* We investigate the security issues arising from the adoption of the crowdsourced model for location tracking.
We define and formalize a set of security properties and conditions that crowdsourced location tracking systems must guarantee.

* We perform a security analysis of the most popular, commercial, crowdsourced tracking systems, demonstrating a real threat for users.
Specifically, by analyzing and instrumenting their mobile apps, we identify major design flaws in all these systems.
We reported our findings to the responsible entities.

* We design , a secure protocol for crowdsourced location tracking that fulfills all our security properties, protecting users from various attacks, and providing end-to-end encryption.
We show the practicality of our approach by implementing and testing a prototype.

In the spirit of open science, we make all our code available at <https://github.com/ucsb-seclab/SECrow>.

There are numerous crowdsourced BLE tracking devices that exist in the market. More and more manufacturers such as Apple have shown interest in making such a product that will increase the adoption of such devices and it's accompanying technology.

To understand the current state of these devices, we analyzed some of the popular devices available in the market. However, none of these devices were secure and often times easy for an attacker to obtain and or spoof parts of the service. This causes a huge risk to the users of such devices as these devices are often used to keep track of valuable items.

And since there have been numerous publications on the security issues with Bluetooth technology, we find that such a system requires more scrutiny regarding the threat it poses to a users privacy.

§ BACKGROUND

In this section, we explain crowdsourced tracking using common terms that will be used throughout the paper.
The goal of crowdsourced tracking is to provide users with the ability to track the location of physical devices by leveraging the crowdsourcing model, , by leveraging information collected and produced by other users in the network.
A typical crowdsourced tracking system involves three entities (Figure <ref>).

* TD: The actual devices being tracked (, TrackR <cit.>, CUBE <cit.>).
These devices are battery-powered, communicate using BLE, and they are compact so that they can be attached to other physical objects, such as wallets and keys.
This provides the ability to track the corresponding physical objects by leveraging the attached TD.

* TS: A web service (usually REST-based <cit.>) provided by the manufacturer of TD that allows users to know the location of their TD.

* CD: A device that can directly communicate with a TD.
Most commonly, this is an Internet-enabled smartphone running an app, which we call TApp, provided by the TD vendors.
The TApp can communicate with the TS and TD.
If the CD has location service capabilities, then the TApp can update TS with the current location of all the BLE-visible TD, , those that are nearby.
This information from CD represents the crowd input.
The information from all the CD is used by the TS to provide the ability for users to know the location of their TD.
The TApp also provides an easy way for users to track TD and thus provides an implicit incentive for the users to install the app, thereby participating in crowdsourced tracking.

Owners. Every TD is owned by one or more users who can perform privileged operations on it, such as make it ring and flash.
The ownership is established by registering and claiming the device through a pairing process, where the TApp adds the  TD as a registered item within the user account.
Generally, users use TApp to interact with owned TD through BLE.
Furthermore, owners can query the last known location of a TD, that is lost or not in BLE proximity, by communicating with the TS—through the TApp.

A representative crowdsourced tracking system is depicted in fig:crowdsourced-tracking-architecture, which shows four TD, four CD, and the TS:
$\ac{CD}_{1}$ and $\ac{CD}_{4}$ own $\ac{TD}_{1}$;
$\ac{CD}_{2}$ owns $\ac{TD}_{2}$ and $\ac{TD}_{3}$;
$\ac{CD}_{3}$ owns $\ac{TD}_{4}$.
The dashed arrow indicates that the user with $\ac{CD}_{1}$ moved from location $loc_{1}$ to $loc_{2}$.

Location update. All CD constantly update the TS with the location of the TD that are in BLE proximity.
Specifically, $\ac{CD}_{1}$ and $\ac{CD}_{2}$ update the location of $\ac{TD}_{2}$ using the tuple $\ac{TD}_{2}$, $loc_{2}$. Similarly, $\ac{CD}_{3}$ updates the location of $\ac{TD}_{3}$ and $\ac{TD}_{4}$.
$\ac{CD}_{4}$ does not send any location update since there are no TD nearby.

Location query. The owners of a TD can query TS about the location of their TD.
The TS responds with the last known location of the TD.
In fig:crowdsourced-tracking-architecture, we can see that $\ac{CD}_{1}$, $\ac{CD}_{2}$, and $\ac{CD}_{4}$ issue location queries for $\ac{TD}_{1}$, $\ac{TD}_{3}$, and $\ac{TD}_{1}$ respectively represented by a tuple of the form $\ac{TD}_{x}, ?$.
TS responds to such location queries with the last known location of the TD in the form $\ac{TD}_{x}$, $loc_{y}$.
CD do not need to send location queries for their TD when they are nearby, as they can communicate directly through BLE.
For instance, $\ac{CD}_{3}$ does not send any location query for $\ac{TD}_{4}$ as it is BLE visible to the corresponding $\ac{CD}_{3}$.

Data-flow of a representative crowdsourced tracking system.
$\ac{CD}_{1}$ and $\ac{CD}_{4}$ own $\ac{TD}_{1}$.
$\ac{CD}_{2}$ owns $\ac{TD}_{2}$ and $\ac{TD}_{3}$.
$\ac{CD}_{3}$ owns $\ac{TD}_{4}$.
The dashed arrow indicates that the user with $\ac{CD}_{1}$ moved from location $loc_{1}$ to $loc_{2}$.

§ SECURITY PROPERTIES

As already mentioned, the main goal of any crowdsourced tracking system is to provide the ability for users to reliably obtain the location of their tracked devices.
From a security and privacy perspective, we also want such systems to guarantee certain properties, , only owners can perform privileged operations.
Furthermore, for each property, we identify the necessary conditions that need to be satisfied to guarantee the corresponding property.
We call these the NSC of a security property.
This can be represented formally as,

\begin{equation*}
\forall C \in NSCs(S) : \lnot C \rightarrow \lnot S.
\label{lab:secp}
\end{equation*}

where $NSCs(S)$ is the set of all the necessary conditions for the security property $S$.
This formulation implies that if any of the NSC does not hold, then the corresponding security property is violated, providing an effective method to check for violations of the security properties.
All the security properties are named as $X-S_{y}$, where $X$ is the entity the security property belongs to, and $y$ is a number indicating a unique id.
Similarly, all the necessary conditions are named as $C_{n}$, where $n$ is a positive number.

Next, we list all the security properties and their corresponding necessary conditions.

§.§ TD security properties

Privileged owners ($TD-S_{1}$). Only owners can perform privileged operations on a TD. Specifically, we consider the following operations as privileged:

* Obtaining the location of the TD from the TS.

* Making the TD ring or blink remotely (, through BLE) to capture human attention.

To enforce the above restrictions, it is important for a TD and the TS to have an ability to recognize the owners of the TD to restrict access to the privileged operations.
Hence, we see that following as the NSC for the $TD-S_{1}$ security property:

* : The TD must able to recognize its owners.

* : The TS must able to recognize the owners of a given TD.

Physical ownership ($TD-S_{2}$). It must be impossible to own a tracking device without physical access.
This is based on the traditional ownership requirement  to own a device, it is important to verify that the device can be accessed physically.
To ensure this, we need the ability to verify physical ownership.
Consequently, we need the following NSC for the $TD-S_{2}$ security property:

* : Owning of a TD must involve performing a physical action on the TD.

* : Registering as a owner of a TD with the TS must involve communicating with the TD.

We assume that once registered to a (primary) owner, a TD cannot be registered to a new (primary) owner.
As we detail in sec:securedesign, we allow primary owners to register secondary owners.

§.§ CD security properties

Anonymous and proximity-aware location update ($CD-S_{1}$). A CD should be able to anonymously update the location of only in proximity TD.
This ensures that participating in the crowdsourced system does not pose any privacy risks for the CD and protects against Sybil attacks <cit.> by ensuring that location can be updated for only those TD that are in BLE proximity
This constrains that all the sybils need to be in BLE proximity of the victim TD.
To guarantee this property, we require that a CD communicates with a TD to update its location.
Since  TD can communicate only through BLE, such communication ensures proximity.
Hence, the NSC is:

* : The CD can update the location of a TD if and only if the CD can communicate with the TD.

§.§ TS security properties

Reliable location service ($TS-S_{1}$). The location information provided by the TS  must be reliable, , the retrieved location of a TD must not be spoofable.
This ensures that the location information about a TD provided by the TS can be trusted by the owners.

To have the $TS-S_{1}$ property, all the entities involved in the location update of a TD (, TD, location information from CD, and, TS) should not be affected.
Which results in the following NSC:

* : It must be impossible to spoof a given TD.

* : It must be impossible to spoof a location by a CD.

* : It must be impossible to spoof the TS[This can be  achieved by ensuring that TS uses TLS <cit.>.].

tbl:securityproperties summarizes the aforementioned security properties along with the corresponding necessary conditions (-), which form the NSC of a secure crowdsourced tracking system.

Security properties of an ideal crowdsourced tracking system along with the corresponding necessary conditions.

4cSecurity properties of a crowdsource tracking system

2cTracking device (TD)     Communication device (CD)     Tracking service (TS)

Privileged owners     Physical ownership     Anonymous & proximity-aware     Reliable location service

($TD-S_{1}$)     ($TD-S_{2}$)     location update ($CD-S_{1}$)     ($TS-S_{1}$)

TD should recognize its owners ()

TS should recognize owners of a given TD ()

Owning a TD should involve performing physical action on it ()

TS should be able to verify proof of physical activity ()

CD can update the location of a TD if and only if the CD can communicate with the TD ()

Impossible to spoof a TD ()

Impossible to spoof a location by CD ()

Impossible to spoof the TS ()

§ THREAT MODEL

In any crowdsourced tracking system, the TS plays a major role as it is the main entity that receives and provides location information for all the TD.
In our work, we consider TS to have malicious but cautious behavior <cit.>. In practice, on the one hand, we assume that the TS does not intentionally attempt to spoof the location information, as users could easily identify tampered location records.
On the other hand, we assume that the TS can actively attempt to collect or learn information about the location of the TD from incoming reports and queries, therefore affecting the users' privacy.

We assume an external attacker that has full control of the software that runs on a CD, except for the code that is protected through hardware isolation mechanisms, such as ARM TrustZone <cit.>.

We consider the TD to be a black box for the attacker. Specifically, the attacker can only communicate with a TD through BLE.
As such, attacks involving physically tampering with the TD and corresponding hardware attacks are out-of-scope for our work.
However, we assume that the attacker can snoop in the BLE traffic and try to mimic a TD.
Finally, we do not consider vulnerabilities in communication protocols implementations such as BLE and TLS.

Similarly, software vulnerabilities in the code that runs in the TS and TD are out-of-scope, and well covered by other research work.
However, we assume that the TS can be subject to data breaches, and thus we aim at protecting location information even in such scenarios—guaranteeing end-to-end encryption.

In our threat model, attackers are interested in accessing or spoofing information about the location of users' valuable objects, with the goal of, for instance, tracking and stealing such valuables.

As mentioned before, the main goal of any crowdsourced tracking system is to provide an ability for users to know the reliable location of tracking devices.
From a security and privacy perspective, we also want certain properties to hold for any crowdsourced tracking system.
Furthermore, for each of the properties, we identify the necessary capabilities required to satisfy the corresponding property.

All security properties are named as X-Sy, where X is the entity for which the security property belongs, and y is a number indicating a unique id.

Similarly, a capability required for a security property with name M is named as M*X-Cy, where X is the entity that needs to have the capability, and y is a number indicating a unique id.

The security properties and the corresponding required capabilities are listed below:
Tracking Device Security:
Privileged owners (TD-S1): Only owners can perform privilege operations on a tracking device. Specifically, we consider the following operations as privileged:
To know the location of the TD from the TS.
To perform ringing or blinking or other actions remotely (, through BLE) that bring human attention to the TD.

The intuition here is to ensure that only owners of a TD be able to access services of the TS w.r.t the corresponding TD.
Required capabilities:
TD-S1*TD-C1: The TD should be able to recognize its owners.
TD-S1*TS-C1: The TS should be able to recognize owners of a given TD.

Physical ownership (TD-S2): It should be impossible to own a tracking device without physical access.

This is based on traditional ownership requirement  to own a device, it is important to ensure that the device can be accessed physically.

Required capabilities:
TD-S2*TD-C1: Owning of a TD should involve performing a physical action on the TD.
TD-S2*TS-C1: The TS should be able to verify the proof of the physical activity on the TD.

Communication Device Security:

Anonymous location update (CD-S1): A CD should be able to anonymously update the location of only in proximity TD .

This ensures that participating in the crowdsource tracking system does not pose any privacy risks to the CD. Furthermore, ensuring that location can be updated for the only those TD that are in BLE proximity enabled protection against Sybil attacks (cite).

Required capabilities:

CD-S1*TS-C1: The CD should be able to update the location of a TD if and only if the TD is in BLE proximity or, in other words, the CD can communicate with the corresponding TD.

Tracking Service Security:
Reliable location service (TS-S1): The location information of TD that is provided by the TS should be reliable. , location of a TD provided by the TS should indeed be the location of the TD.

This ensures that the location information about a TD provided by the TS is reliable and can be trusted by the owners.

Required capabilities:
TS-S1-TD-C1: It should be impossible to spoof a given TD.
TS-S1-CD-C1: It should be impossible to spoof a location by a CD.
TS-S1-TS-C1: It should be impossible to spoof the TS.

For each of the above properties to hold, we need to have certain necessary conditions that should be satisfied.
Specifically, these are the conditions if not satisfied, then it impossible to design a crowdsource tracking system that can achieve all the above properties.
The TD should be able to recognize its owners.
The TS should be able to recognize owners of a given TD.
Owning of a TD should involve performing a physical action on the TD.
The TS should be able to verify the proof of the physical activity on the TD.
The CD should be able to update the location of a TD if and only if the TD is in BLE proximity or, in other words, the CD can communicate with the corresponding TD.
It should be impossible to spoof a given TD.
It should be impossible to spoof a location by a CD.
It should be impossible to spoof the TS.

§ SECURITY ANALYSIS

We study five popular crowdsourced tracking systems, TrackR <cit.>, CUBE <cit.>, Chipolo <cit.>, Pebblebee <cit.>, and, Tile <cit.>, looking at whether each system guarantees the aforementioned security properties (subsub:securityprop).
We do so by verifying if all the NSC hold.
All of the studied systems provide a TApp that users can use to communicate with the TD and the corresponding TS (tbl:crowdtrackingdataset).
Users must first create an account by registering with the TS.
All communications with the TS then require the user to login and include their session token in every request sent to the TS.
We use the term authenticated REST endpoint to indicate that the endpoint requires the user to authenticate first.
Some tracking services allow a TD to have multiple owners so that multiple users can share and track a TD.
Note that, there exist other BLE tracking systems, such as GoFinder HL <cit.> and Nut <cit.>, which, however, do not adopt the crowdsourced model and, hence, are out-of-scope for this study.

§.§ Methodology

Our analysis methodology is based on the following two steps.

We record the messages sent from the TApp to the TD and TS.
First, we manually reverse engineer the TApp to identify the functions used to send and receive messages from and to the TS and TD.
For instance, the TrackR's TApp uses the  method of the  class to send messages to the TS.
Next, we setup a dynamic instrumentation environment to hook into the identified functions and record all their messages.
Finally, we use the corresponding TApp to register a TD, update its location from a different CD, and retrieve the updated location.
Our dynamic instrumentation records all the messages sent through the instrumented functions.
We carefully select the appropriate functions to hook so that we get messages in plaintext before they encrypted <cit.>.
Thus, hooking at lower layers (, system calls) might not reveal the content of the messages.

We report the details of the communication endpoints of each tracking system in the Appendix of our full version <cit.>.

We use recorded messages to test the required security properties.
For instance, consider the case of verifying the physical ownership property for CUBE.
We purchased two CUBE TD, $D1$, and $D2$, whose Bluetooth MAC address is respectively  and .
During our recording phase, we record that, when registering a new owner for $D1$, the TApp sends an HTTP POST request to the endpoint  with the following JSON payload: .

We can see that the payload includes the MAC address of $D1$ (, ) and we do not see any communication with $D1$, which violates NSC $\capfour{}$.
Now, to verify the physical ownership in CUBE, we replay the request by replacing the MAC address with .
A successful request indicates that we can register a new owner for the TD without physical access, thus violating the physical ownership property ($TD-S_{2}$).
We follow the same black-box methodology to verify each property for each tracking system.

In the following sections, we describe the results of our analysis of the studied crowdsourced tracking systems, and we show that none of them guarantee the desired security properties.

Crowdsourced tracking systems considered in our security analysis.

Tracking             Multi-owner

System     TApp     TS     Support

black!15 TrackR <cit.>               com.phonehalo.itemtracker <cit.>       <platform.thetrackr.com>     Yes

CUBE <cit.>                 com.blueskyhomesales.cube <cit.>       <net.cubetracker.com>      No

black!15 Chipolo <cit.>             chipolo.net.v3 <cit.>        <api.chipolo.net>      No

Pebblebee <cit.>            com.pebblebee.app.hive3 <cit.>      <api.pebblebee.com>     No

black!15 Tile <cit.>               com.thetileapp.tile  <cit.>       <production.tile-api.com>     No

§.§ TrackR

Owner registration.

A user can own a TD by pairing with it
through BLE.
Furthermore, the user also needs to send a  request to TS to register as an owner of the TD.
Specifically, the registration request is sent to the REST endpoint with a JSON payload containing a unique identifier, called , of the TD along with  .
Here,  is the login token of the user, and the  of the TD is a string composed of four zeros (“0000") and the reverse of the Bluetooth MAC address of the TD.
For instance, for a TD with MAC address 00:1B:44:11:3A:B7, the  is 0000b73a-11441b00.

This design violates both the Privileged owners ($TD-S_{1}$) and the Physical ownership ($TD-S_{2}$) properties.
In fact, the TD, in the case of TrackR, does not keep track of the owners resulting in missing  NSC.
Because of this, an attacker can perform privileged operations, such as ringing and blink, on the TD by sending messages over BLE to the TD.
Second, as mentioned above, registering as an owner of a TD requires an attacker to send a POST request with the attacker's login token and the  of the TD.
However, the  of a TD can be easily obtained by observing its MAC address, which is broadcasted over Bluetooth and can be known without physical access to the TD.
Thus an attacker can register as an owner of any nearby TD, which violates missing  and  NSC.
Moreover, given that the first three bytes are unique for an organization <cit.>, , TrackR, by knowing a MAC address an attacker can use the last three bytes to enumerate all possible TrackR TD MAC addresses and register as an owner for every TrackR TD without having physical access to the TD, thus violating Physical ownership property.

Location update.

Updating the location of a TD to the TS is done by sending a PUT request to the REST interface with a JSON payload containing the  of the TD along with location information in the form of longitude and latitude values.

This allows an attacker to update the location information of any TD (given its MAC address) without being physically close to the TD.
Note that, updating the location of TD does not require communicating with the TD, consequently missing  NSC.
This violates the Anonymous and proximity-aware location update ($CD-S_{1}$) property.

Location query.
A user can obtain the location of a TD by sending a GET request to the REST interface using the login token of the user.
The TS responds with location information of all the TD owned by the user.
Given a TD, an attacker can affect the TD's location information either by updating its location using the method described in subsub:trackrlocupdate or by spoofing the MAC address of the TD (, missing  NSC).
Moreover, the TS blindly trusts the location information about a TD provided by any user without verifying the accuracy of the location information missing  NSC.

These attacks clearly violate the Reliable location service ($TS-S_{1}$) property.

§.§ CUBE

Owner registration.
A new owner can register by pairing with the TD and sending a POST request to the TS, through an authenticated REST endpoint. The payload of this request contains the MAC address of the TD along with other data items.

The TS allows a single owner to a given TD. Hence, the TS allows a user to register as the owner of a TD only if the TD is not already registered by another user. However, the TS does not verify that the user has physical access to the TD. This enables an attacker to own an unregistered TD by knowing its MAC address.
This  violates the Physical ownership ($TD-S_{2}$) property. Furthermore, as mentioned in subsub:trackraddowners, from a single MAC address of a CD an attacker can enumerate all the possible MAC address of the TD and register as the owner before a valid user attempts to register.

Similarly to TrackR, the TD in CUBE do not keep track of their owner (, missing ). This allows an attacker to perform privileged operations, such as ringing and blink, on the TD, thus violating the Privileged owners ($TD-S_{1}$) property.

Location update.

In CUBE, location updates by a user are accepted for a TD only if either the TD is owned by the same user or the TD is marked as lost by their respective owners.
The location update of a TD is sent to the TS using a PUT request with a JSON body containing the device MAC address and location information.

Similar to TrackR, the CUBE TS blindly trust the location information about a TD provided by any user without verifying neither the accuracy of the location information (, missing ) not the physical proximity of the TD ( missing ).
This violates the Anonymous and proximity-aware location update ($CD-S_{1}$) property as an attacker can update and spoof the location of any TD without being physically close to them.

Location query.
The location of a TD can be obtained by sending a GET request along with the emailID of the user account.
This returns the location of all the TD registered by the user.

Similar to TrackR, in the case of CUBE, an attacker can affect the TD's location information either by updating the location using the method described in subsub:cubelocupdate or by spoofing MAC address of the TD (, missing ).
These attacks clearly violate the Reliable location service ($TS-S_{1}$) property.

§.§ Chipolo

In Chipolo, the TS assigns to every TD and user a unique id, called , which is used by the users to communicate with the TS on behalf of the TD.

Owner registration.
In Chipolo, similar to other tracking systems, a TD can be owned by first pairing with it.
However, registering the ownership of a TD to the TS requires two REST calls.
To register as the owner for a TD, first, the user needs to send a GET request containing the unique id assigned to the user on account registration and the Bluetooth MAC address of the TD.

If the TD is not registered TS sends a one-time secret device token.
Next, the user needs to make a POST request with JSON payload containing the above secret token.
On successful registration, TS sends a JSON response with a success message containing the  that can be used for all future communication with TS concerning the TD.
However, similar to other tracking systems, the TS does not verify that the CD can communicate with the TD (, missing ).
This enables an attacker to own an unregistered TD by only knowing its MAC address, which does not require physical access.
This  violates the Physical ownership ($TD-S_{2}$) property

Furthermore, unlike other tracking systems, only owners , paired users, can send privilege commands (using a CD) to a TD, thus preserving the Privileged owners ($TD-S_{1}$) property.

Location update.

Similarly to owner registration, updating the location of a TD requires two REST calls.
To update the location of a TD, first, a GET request should be sent with the unique id for the user and , which is an identifier broadcasted by the TD through one of the advertised packets.

This GET request returns the , which is then used in the second PUT request to the authenticated REST endpoint, with the payload containing the location information.

Similar to other systems, the TS of Chipolo blindly trusts the location information about a TD provided by any user without verifying neither the accuracy of the location information (, missing ) nor the physical proximity of the TD (, missing ).
Consequently, this violates the Anonymous and proximity-aware location update ($CD-S_{1}$) property.

Location query.
A user can obtain the location information of all the TD by sending a GET request, which returns a JSON response containing the location information of all the TD owned by the user corresponding to .

As explained in subsub:chipololocupdate, given the MAC address of a TD,
an attacker can update the location of the TD, thereby compromising the integrity of location information.
Thus violating the Reliable location service ($TS-S_{1}$) property.

§.§ Pebblebee

Owner registration.
To register as the owner of a TD, a user needs to first pair with the TD through BLE.
To register with the TS, a POST request needs to be sent with the Bluetooth MAC address of the TD.
During registration, the TS does not verify that the user can communicate with the TD, consequently missing .
This enables an attacker to own an unregistered TD by knowing its MAC address, which does not require physical access, and, therefore, violates the Physical ownership ($TD-S_{2}$) property.

Similar to TrackR and CUBE, the TD in the case of Pebblebee does not keep track of the owner (, missing ) which enables an attacker to perform privileged operations, such as ringing and blink, on the TD by sending messages over BLE, thus violating the Privileged owners ($TD-S_{1}$) property.

Location update.

In Pebblebee, location update of a TD is done by sending a POST request with a JSON payload containing the location information along with the MAC address of the TD.

Similar to other systems, the TS of Pebblebee does not verify either the accuracy of the location information (, missing ) nor the physical proximity of the TD (, missing ).
Consequently, this violates the Anonymous and proximity-aware location update ($CD-S_{1}$) property.

Location query.
The location query in Pebblebee is done by sending a GET request, with the Bluetooth MAC address of the TD.
Unfortunately, given the  of a TD, any user can query the location (a privileged operation) of the TD using the above URL.
Furthermore, as explained in subsub:trackraddowners, from a single MAC address of a TD, it is easy to enumerate the MAC address of all TD.
Consequently, an attacker can perform location query of all TD, which further violates the Privileged owners ($TD-S_{1}$) property.

Given that an attacker can arbitrary update the location of any TD (subsub:pebblelocupdate), this affects the integrity of location information.
Thus violating the Reliable location service ($TS-S_{1}$) property.

§.§ Tile

Owner registration.

Similar to the other systems, TD in Tile needs to be first paired through BLE using TApp,
which will then register with  TS by sending a PUT request to it's API interface at <https://production.tile-api.com/api/v1/>.

Along with this request, a unique signature and static client uuid are added.
This requires the TD to be physically present near the CD.

Unlike other systems, once a Tile is added it cannot be deleted by the owner.

The owner, however does have other options such as to hide TD temporarily,
transfer it to another user using their email address and replace an existing Tile with a new Tile.
The owner registration process of Tile is the most secure design of all the analyzed systems.
In fact, our design as explained in subsec:ownerregis is inspired by Tile.

Location update

In Tile, location updates are encrypted and updated by sending a POST request to the TS.
But, only logged in users can send the location update request thereby violating the Anonymous and proximity-aware location update ($CD-S_{1}$) property.

Location query
Location query in Tile is done by sending a authenticated GET request, with requesting client uuid, and a tile request signature of the CD.
Furthermore, only owner can query the location of a TD.

Finally, given that the location information is blindly trusted. An attacker
can update all in-proximity TDs with random locations thereby violating the Reliable location service ($TS-S_{1}$) property.

Verified security properties for each device, where 51 and 55 in each cell indicate whether the corresponding security property holds or not respectively. The NSC ($C_{x}$) under 55 indicates the missing conditions (subsub:securityprop).

4cSecurity Properties of a crowdsourced tracking system

2c Tracking device (TD)     Communication device (CD)     Tracking service (TS)

Device manufacturer
Privileged owners
Physical ownership
Anonymous and proximity-aware location update
Reliable location service

black!15 TrackR     55 ()     55 (, )     55 ()     55 (, )

CUBE     55 ()     55 (, )     55 ()     55 (, )

black!15 Chipolo     51     55 (, )     55 ()     55 ()

Pebblebee     55 ()     55 (, )     55 ()     55 (, )

black!15 Tile     51     51     55 ()     55 ()

§.§ Summary

tab:verifiedsecurityproperties summarizes the results of our analysis.

We verified all our findings by implementing a PoC for each violation.
Interestingly, all the tacking systems satisfy two NSC, ,  (TS able to recognize owners of a CD) and  (Impossible to spoof the TS), which they achieve by using HTTPS for their communications.

Our results show that, except for the Privileged owners ($TD-S_{1}$) property in Chipolo, none of analyzed tracking systems guarantee the desired security properties.

Responsible disclosure.
All the device vendors have been contacted and notified regarding the security issues discussed in the paper.
Two vendors already replied and acknowledged our findings.
We have not heard back from the remaining two vendors yet.

§.§ Tile

The Tile is the most popular crowdsource tracking system that has claimed over 90% of the market share of all bluetooth tracking devices.
TD in Tile are small BLE enabled, battery-powered devices that can emit a low-pitched sound to help to easily recognize it.
The Tile devices are available as independent bluetooth tracking devices as well as come built into varios products from manufacturers such as Bose, HP, Plantronics, Sennheiser, Herschel, The wide availability of Tile devices and users makes it far and large the most popular and useful crowdsource network able to geolocate devices.

TD properties:

§.§.§ Owner registration

Using the application provided, the user initiates the add process for a Tile. This pairs the Tile and sends a PUT request to it's API interface <https://production.tile-api.com/api/v1/> to register the device. Once the registeration process is complete the Tile is permanently added to the users account. Once a Tile is added it cannot be deleted by the owner. Tile only allows customer support to delete a Tile from an account making the Tile unusable for further use. This is noted as a nuclear option. An owner, however does have other options such as hiding a Tile temporarily, transfer it to another user using their email address and replace an existing Tile with a new Tile.

CD properties:

§.§.§ Location update

TS properties:

§.§.§ Location query

§ SECURE TRACKING SERVICE

In this section, we present , a crowdsourced tracking system that satisfies all the desired security properties.
Similar to the existing systems, the TS in  requires any user to register and log in before using the system.
Furthermore, the TS keeps track of the ownership association , the set of owners of a TD, and is also able to recognize an owner of a TD. This satisfies our NSC .
Furthermore, the TS uses TLS for all its communication, thereby making it impossible to spoof a TS, which satisfies NSC .

Not sure if the certificates part could backfire, we do not say enoungh (e.g., are these certificates verified/signed? is there a CA?)

§.§ Public key cryptography

One of the main building blocks of  is the public key cryptography <cit.>.
Specifically, every entity in our system, , TS, CD, and, TD, has a public key and private key pair.
As in all public key cryptographic systems, the public key of an entity is available to the other entities through certificates.
The private key is, instead, secret and only known to the corresponding entity.

We use the following notations for various cryptographic primitives.
$Pk_{x}$ and $Pr_{x}$ indicate public and private key of entity $x$.
$Enc(K, P)$ and $Sign(R, P)$ indicates encryption of content $P$ with public key $K$ and signature of $P$ with $R$, in the case of RSA this is same as encryption of $P$ with private key $R$.
Since encryption with the private key is called a signature, we use $Sign$ to indicate encryption with a private key.
Also, $SEnc(S, P)$ indicates encryption with the symmetric key $S$
$X_{I}$ indicates a unique identifier (ID) for the entity $X$.
For instance, this could be the Bluetooth MAC address for a TD, and the user $ID$ of the logged-in user
for a CD.

§.§ Built in capabilities

In , we assume the TD and CD to have certain capabilities, which allow them to provide the required security properties.

TD capabilities.

The TD has its private key etched on to on-chip read-only memory, such as e-fuses <cit.>. Thus, to spoof a given TD, one needs access to its private key, which is impossible without physically invasive techniques <cit.>.
The TD also has a small amount of persistent storage and the ability to generate random numbers.
The persistent storage contains the location key (, $L_{\ac{TD}}$), which is used as the symmetric key to encrypt and decrypt location data of the TD (4 in fig:seclocupdate).
The persistent storage also contains the public key certificates of all the owners of the TD.
This enables a TD to verify whether a given CD is one of its owners and thus to satisfy the NSC .
Every TD has a single primary owner and can have multiple secondary owners.
The primary owner has additional privileges and can regulate the secondary owners of the TD.

CD capabilities.

All the location updates in  have to be signed.
Since CD (, smartphones) are commonly used to communicate with the TS, CD have to be able to provide signed location (GPS) information.
Furthermore, the CD operating system must not be able to tamper the location information.
This can be achieved by using existing techniques <cit.> that leverage TEE, such as ARM TrustZone <cit.>, which is now available across almost all the smartphone brands <cit.>.
Furthermore, CD have the ability to create temporary but attested public-private key pairs, denoted as $TPk_{CD}$ and $TPr_{CD}$, which are managed by a TEE and cannot be tampered with by the user operating system <cit.>.
As we show in subsub:locupdate, these keys are used to provide anonymous but signed location information.
In this scheme, the CD cannot provide fake location information, therefore satisfying one of the NSC, , .

§.§ Owner registration

In , adding owners to a TD requires the TD to be in pairing mode, which is only possible by physically holding down a dedicated button on the TD. This satisfies  NSC (subsub:tdproperties).
fig:secownerregister shows the sequence diagram of the protocol used in  to add the primary owner to a TD and the TS.

The first block Adding Primary Owner shows the messages exchanged when a CD (or user) requests to be added as the owner of the TD.
When a  request along with the public key, $Pk_{CD}$, is received by a TD, the TD sends a challenge nonce $N_{1}$ back to the CD. The CD is expected to sign the nonce $N_{1}$ to prove that it has access to the private key of the corresponding public key sent in the initial message. On successful verification of the signature by the TD, the TD adds the pubic key $Pk_{CD}$ as the primary owner.
The  request is accepted by a TD only when there is no primary owner yet in the TD.
The primary owner can add secondary owners using the  command (subsubsec:primaryownercmds).

Registering as an owner (either primary or secondary) of a TD to the TS requires three interactions, as indicated by the bottom three blocks in fig:secownerregister.
First, the CD sends a  request along with its ID ($CD_{I}$) and the ID of the TD ($TD_{I}$) to the TS.
The TS replies with a nonce $N_{2}$ and a temporary symmetric key $OT_{K}$ both encrypted with the public key of $\ac{TD}_{I}$ (, $O_{T}$).
Second (), the CD relays $O_{T}$ along with its public key $Pk_{CD}$ to the TD.
The TD decrypts $O_{T}$ (as it has the private key $Pr_{\ac{TD}}$) to retrieve $N_{2}$ and the temporary symmetric key $OT_{K}$.
Using this temporary key, $OT_{K}$, the TD sends back an encrypted message ($O_{CD}$) that includes the public key of the owner ($Pk_{oCD}$), the decrypted nonce ($N_{2}$), and, an additional nonce for freshness ($N_{3}$).
Here, $Pk_{oCD} = Pk_{CD}$, if $Pk_{CD}$ is one of the owners of the TD, else $Pk_{oCD}$ is the public key of one of the registered owners.
The use of $OT_{K}$ for encryption ensures that only the TS can know the owner information of the TD, thereby protecting the privacy of the TD.
Furthermore, the freshness token $N3$ prevents inference attacks.
Finally, in , the CD relays $O_{CD}$ to the TS.
The TS decrypts $O_{CD}$ as it has access to the private key of TD (subsub:cryptoassumptions), retrieves the $Pk_{oCD}$, verifies that the decrypted nonce matches $N_{2}$, and, discards $N_{3}$.

If the $Pk_{oCD}$ is the public key of $\ac{CD}_{I}$ then TS adds $\ac{CD}_{I}$ as one of the owners of the TD (or $\ac{TD}_{I}$).
The validation of the nonce $N_{2}$, through $O_{CD}$, ensures that the ownership request is approved by the TD, therefore satisfying our  NSC.

The protocol described above satisfies the Physical ownership ($\ac{TD}-S_{2}$) property, , it is impossible to own a tracking device without physical access.
This is because, first, adding an owner to a TD requires the TD to be in pairing mode, which is only possible by physically pressing a button on the TD.
Second, to register to the TS, the CD must be able to provide a valid $O_{CD}$, , the public key of the owner and correct nonce ($N_{2}$), encrypted with the temporary symmetric key $OT_{K}$.

The CD cannot produce a valid $O_{CD}$ because it requires access to $N_{2}$ and $OT_{K}$, but, both are encrypted ($O_{T}$) with the public key of TD.
However, generating a valid $O_{CD}$ from $O_{T}$ is possible by communicating with the TD (  of fig:secownerregister).
Note that, the TD generates a valid $O_{CD}$ containing the public key of the CD if and only if the CD is one of its owners. As mentioned before, adding owners requires physical access.
Instead, if the CD is not an owner of the TD, the TD still produces a valid $O_{T}$, but containing the public key of a real owner.

Primary owner commands.

As mentioned in subsubsec:tdcapabilities, the primary owner of a TD has additional privileges.
Specifically, primary owners can issue the following commands:
(1)   to update the location key (, $L_{\ac{TD}}$) of the TD; (2)  &  to add or remove secondary owners of the TD.

Each of the above commands involves a challenge nonce issued by the TD, which is encrypted with the stored public key of the primary owner.
The requesting CD can decrypt the message and obtain the nonce only if it is indeed the primary owner.
The decrypted nonce is used to authenticate the following requests.
fig:updatedevicesecret shows the flow of the  procedure in .
Here, when the command is issued by a CD (1), the TD responds (2) back with an encrypted random nonce ($E_{n}$)—encrypted with the stored public key of the primary owner ($Pk_{pCD}$).
The CD, if it is the primary owner (, the CD has the corresponding private key), can decrypt $E_{n}$ to retrieve $N$.
The CD now uses $N$ to send the data (3) of the request ($R$) to the TD, , the location key $L_{TD}$ along with $N$, both encrypted with the public key of the TD.
Finally, the TD, after receiving $R$, decrypts and verifies the nonce $N$. On a successful match, the TD stores the provided key, $L_{TD}$, as the location key.
As we show in subsec:locquery, the location key of a TD is required to obtain the latest location of the TD.
We consider that primary owner to be responsible for sharing the location key with secondary owners.
This provides the primary owner an access control mechanism to regulate who (secondary owners) can access the location information of the TD.
Note that, by using a random nonce, our design is not vulnerable to replay attacks.

The commands  and  follow a procedure similar to the one shown in fig:updatedevicesecret. However, in the request data $R$, the primary owner sends the public key of the CD to be added or removed instead of the location key.

every picture/.append style=

transform shape,

CDCD (ID: $\ac{CD}_{I}$)
[1.4]TDTD (ID: $\ac{TD}_{I}$)

Updating Device Secret

CD1 UpdateLocKey
TD2 $E_{n}=Enc(Pk_{pCD}, N)$

CD3 $R=Enc(Pk_{TD}, N||L_{TD})$

Updating the location key of a TD in

§.§ Location update

In , we aim to guarantee the Anonymous and proximity-aware location update ($CD-S_{1}$) property, , a CD should be able to anonymously update the location of a TD if and only if it is in BLE proximity of the TD.
fig:seclocupdate shows the sequence diagram of the protocol used to update the location of a TD in .

First, the CD sends a  to the TS.
This request contains the temporary and attested public-key ($TPk_{CD}$) of the CD and the ID of the TD whose location needs to be updated.
The public-key $TPk_{CD}$ comes with a certificate chain.
The root certificate within this chain is signed using an attestation root key,
which the device manufacturer injects into the device's hardware-backed keystore at the factory <cit.>.
The TS responds back with two nonces, $N_{t}$ ($E_{T}$) and $N_{c}$ ($E_{C}$), which are encrypted with the public key of TD and CD respectively.

Next, as shown in the  block, the CD, interacting with the TEE, decrypts $E_{C}$ to get $N_{c}$.
The nonce $N_{c}$ along with the location information () is signed by the TEE with the temporary private key ($TPr_{CD}$), resulting in $L$.
The CD forwards the encrypted nonce $E_{T}$, $TPk_{CD}$, and $L$ to the TD (3).
The TD verifies $L$ using $TPk_{CD}$ and decrypts $E_{T}$ to get the nonce $N_{t}$.

Next, the TD encrypts the location  and a random nonce $N_{l}$ using the location key to get $E_{L}$, and then signs both nonces, $N_{t}$ (decrypted from $E_{T}$) and $N_{c}$ (retrieved from $L$), to generate $S_{T}$.
Both $E_{L}$ and $S_{T}$ are then sent to the CD (4).
The random nonce, $N_{l}$, acts as a freshness token and avoid inference attacks.

Finally, as shown in  block, the CD forwards $E_{L}$ and $S_{T}$ to TS (5). The TS verifies $S_{T}$ to check that the signatures are valid and contain expected nonces.
Consequently, it updates its database with the location of the TD to be $E_{L}$.

Note that the requirement of a valid $S_{T}$ satisfies our  NSC.
In fact, to generate a valid $S_{T}$, the CD must communicate with the TD, and, hence, it has to be in BLE proximity.
The described location update protocol satisfies our Anonymous and proximity-aware location update ($CD-S_{1}$) property.
First, the use of temporary keys ensures the anonymity of the CD.
Second, to perform a location update, as shown in  block of fig:seclocupdate, the CD is expected to send $S_{T}$, which contains the nonces $N_{t} || N_{c}$ signed with the private key of the TD.
Thus, the CD can produce a valid $S_{T}$ only by communicating with the TD.

Furthermore, the location information of a TD is stored on the TS in encrypted form (, $E_{L}$), and the decryption key is unknown to the TS.
This design guarantees end-to-end encryption, protecting the private information (, location) of the TD.

every picture/.append style=

transform shape,

[1.1]CDCD (ID: $\ac{CD}_{I}$)
[2.6]TDTD (ID: $\ac{TD}_{I}$)

Adding Primary OwnerTD in Pairing Mode
TD has no primary owner

CD1 AddPOwner, $Pk_{CD}$
TD2 $N_{1}$

CD3 $U_{CD}=Sign(Pr_{CD}, N_{1})$

Add Owner Request

CD4 AddOwner, $\ac{CD}_{I}, \ac{TD}_{I}$
TS5 $O_{T}=$
$Enc(Pk_{TD}, N_{2}||OT_{K})$

CD Owner Query

CD6 CheckOwner, $Pk_{CD}$, $O_{T}$
TD7 $O_{CD}=SEnc(OT_{K}, Pk_{oCD}||N_{2}||N_{3})$

Commit Owner

CD8 $O_{CD}$

Secure owner registration of

§.§ Location query

We want only the owners of a TD to be able to successfully retrieve its location from the TS, as this is a privileged operation.

In , location query by a CD (or user) happens by first authenticating the CD with the TS.
We use a simple challenge-response for authentication.

On successful authentication, the TS then checks whether the authenticated CD is the owner of the TD.
If yes, the TS responds back with the encrypted location token, , $E_{T} = Enc(Pk_{CD}, E_{L}||N)$, where $E_{L}$ is the last-known encrypted location (subsub:locupdate) of the requested TD, and, $N$ is a randomly generated nonce that acts as salt to prevent against dictionary attacks to determine whether the location has changed or not.

Then, the CD decrypts $E_{T}$ with its private key to obtain $E_{L}$.
The CD can now use the location key ($L_{TD}$), previously shared with the TD, to decrypt $E_{L}$ and obtain the location of the TD.
As mentioned in subsubsec:primaryownercmds, the location key is never shared with the TS.
Instead, such a key has to be independently shared by the primary owner of the TD with the other secondary owners.

In summary, our location query protocol satisfies our Privileged owners ($TD-S_{1}$) property, because, to perform a location query, the CD is expected to be the registered privileged owner of the TD.
Furthermore, the nonce $N$ is randomly generated for each request, thus making it impossible for a non-owner CD to infer whether the location of a TD has changed or not.

every picture/.append style=

transform shape,

[2.2]CDCD (ID: $\ac{CD}_{I}$)
[1.6]TDTD (ID: $\ac{TD}_{I}$)

Location update request

CD1 LocUpdate, $\ac{TD}_{I}, TPk_{CD}$
TS2 $E_{C}=Enc(TPk_{CD}, N_{c})$
$E_{T}=Enc(Pk_{TD}, N_{t})$

Sign Token

CD3 $E_{T}, TPk_{CD}$
$L=Sign(TPr_{CD},loc||N_{c})$TD4 $S_{T}=Sign(Pr_{TD}, N_{t} || N_{c})$
$E_{L} = SEnc(L_{TD}, loc||N_{l})$

Attested Location Update

CD5$S_{T}, E_{L}$TS6 Ack

Secure Location Update of

We did a preliminary implementation of using Raspberry Pi 3B with BLE as our TD.
We implemented python based implementations of the CD and TS functionalities.

The TS knows the public keys of all TD.

§ EVALUATION

We implemented a preliminary prototype of using a Raspberry Pi 3B <cit.> with BLE as our TD.
We implemented the CD and TS functionalities in Python.

In this section, we evaluate the performance overhead of in terms of execution time and energy consumption.
We measure the time overhead that affects the CD, as it initiates all the operations.
Whereas for energy consumption, we look at the TD as it has strict power requirements. Specifically, we measure how much additional energy is consumed by compared to the baseline system.
We use a power meter <cit.> to measure the energy consumed by the TD (, Raspberry Pi 3B).

We consider the unmodified TrackR system to be our baseline.

Cryptographic operations overhead.
We measure the overhead of the individual cryptographic operations on the CD, TD, and TS.
tab:microtimings shows the time required for each of the cryptographic operations along with the processors' speed.
These times are very small compared to the frequency of location update and query operations.
In fact, almost all the TApp limit the frequency of such operations to once in 5 minutes.

Execution time of the cryptographic operations (64 bytes of data with 1024-bit keys) performed on each of the entities in our implementation.

4cTime (ms)

TS/CD (2.6 Ghz)     3.0007e-03     2.9787e-03     0.23     0.55

TD (1.2 Ghz)     6.0101e-02     5.1594e-02     4.36     11.98

End-to-End overhead.
We measure the end-to-end overhead introduced to our system, compared to our baseline (i.e., TrackR).
As all the operations start and end at CD, the timings are measured at the CD.
tab:timerecoding shows the time required by each of the operations in compared to the baseline.
Although the time is significantly higher compared to the baseline, the absolute numbers are still small and fall well within operational range (i.e., about 5 min).
Furthermore, additional network communication (both BLE and Ethernet) in  is the main contributor for the time overhead as the time for cryptographic operations is significantly low (tab:microtimings).
The power consumption of the TD for each operation is shown in tab:energyconsumed.
Here, we multiply the average wattage of the TD by the total amount of time of the corresponding operation.
Thus, this represents an upper bound.
In practice, given that most of the time is spent in the network communication between the CD and TS, the actual power consumed by the TD can be significantly lower.
Furthermore, these numbers are again negligible if compared to the capacity of the modern batteries employed by the TD.

The performance numbers reported in our evaluation serve as an upper bound.
This is because, first, our implementation was not optimized and done mainly as a proof of work to test the protocols.

Second, using a Raspberry Pi 3B as a  TD implied that our reported energy consumption is significantly higher than an implementation on a standard BLE device.
Finally, the adoption of specialized low power cryptographic processors <cit.> on the TD would significantly reduce the energy consumption.

Average (10 runs) execution time of each operation.

4cTime (seconds)

Primary Owner

Baseline     0.0346     N/A     0.0386     0.0002

4.4298     4.7319     8.6322     0.1851

Average (10 runs) energy consumed by the TD.

4cEnergy consumed by the TD (Joules)

Primary Owner

Baseline               0.0005          N/A          1.66E-04          0

5.5976          6.7455            11.8824           0

§ LIMITATIONS

relies on various communication protocols, such as TLS and BLE and implicitly assumes them to be secure.
Consequently, is susceptible to any vulnerabilities <cit.> in these protocols.
There are also other limitations of that are listed below:

Built in capabilities. there requires the CD and TD to have a few in-built capabilities (subsec:builtincapabilities).

One of the important capabilities expected from a TD is the ability to perform cryptographic operations.
Given that TD are battery-powered, the cryptographic operations need to be optimized to reduce power consumption.
Low-power cryptographic processors are well-studied <cit.> and are used in various battery-powered devices <cit.>.
These cryptographic co-processors <cit.> can be used to enable TD to perform cryptographic operations without significantly affecting their battery life.

Relay attacks. Similar to contact-less systems, we assume that the ability to communicate with a TD implies proximity.
However, attackers can leverage relay attacks <cit.> to break this assumption.
In practice, a CD (proxy) could serve as a relay to a TD and could enable other CD to communicate with the TD without being in BLE proximity.
Although techniques such as distance bounding <cit.>, secure distance measurement <cit.>, or an out-of-band hardware token <cit.> could be used to prevent these attacks, the low energy requirement of the TD makes the existing solutions impractical.

Denial-of-Service attacks. As a CD can induce a TD to perform cryptographic operations (, 3, 4 in fig:seclocupdate), a malicious and in-proximity CD could drain the battery of a TD by issuing a high number of requests.
However, these attacks can be easily prevented by implementing well-known rate-limiting techniques <cit.>.

§ RELATED WORK

The problem of effective geolocation has been well-studied.
Initial works expect the devices to have the ability to communicate with a remote server <cit.> or the availability of trusted landmarks <cit.>. Both of which are not feasible in our scenario.

Crowdsourced tracking.
Decentralized techniques such as crowdsourcing are used to track lost objects using location-enabled smartphones <cit.>.

SecureFind <cit.> provides privacy for the objects being tracked, wherein it prevents the service from accurately knowing lost devices by making the nodes (i.e., smartphones) send dummy updates to object queries.

However, in SecureFind any user can determine whether a tracker device is lost, which is a privacy concern.

Anonysense <cit.> uses differential privacy techniques such as group signatures <cit.> to provide anonymity for the smartphones that upload location reports.
These techniques have high deployment overhead as they need an end-to-end infrastructure change, including trusted intermediate services.

Techu <cit.> takes a first step toward exploring the security issues in crowdsourced location tracking.
However, the focus in Techu is mainly on the privacy of the CD and TD.
Moreover, their threat model less strict than ours and does not consider the issues of tracking device proximity and location spoofing, which could lead to Sybil attacks <cit.>.
Furthermore, their solution proposes a pull model for location query, where a CD has to communicate with the other CD that performed the location update to retrieve the location.
This introduces additional attack vectors to a CD, as it has to accept incoming connections to perform a location update.
Recently Apple proposed FindMy service <cit.>, which requires the TD to set up an initial key pair (ECP-224) with iCloud server.
To achieve this, the TD needs to have WIFI connectivity to communicate with the iCloud server,
and it requires an input mechanism for a user to enter her credentials.
Unfortunately, the BLE tracking devices that we study in our paper have none
of the capabilities (internet connectivity and input mechanism).
Similarly, several privacy-preserving contact tracing <cit.> techniques also expect geolocation and networking capabilities, which are unfortunately not available on BLE tracking devices.

Another recent work, PrivateFind <cit.> performs a more detailed analysis of the security issues in Bluetooth finders.
They did an excellent job in analyzing various trackers and further, propose a privacy-friendly tracking system.
In this work, we broaden the analysis by considering all the security aspects of a crowdsourced tracking system.
We identify all the necessary properties (subsub:securityprop) of a secure crowdsourced tracking system, which enable a systematic security evaluation of existing crowdsourced tracking systems (tab:verifiedsecurityproperties).
Furthermore, our system, , has additional security guarantees such as resilience to Sybil attacks, which are missing in PrivateFind.

Bluetooth attacks.
There is a considerable amount of work that studies the security of the Bluetooth protocol <cit.>.

Recently, Antonioli et al. <cit.> identified a series of security flaws in the specification of Bluetooth authentication and secure connection establishment, that allows attackers to impersonate Bluetooth devices.

Geolocation and privacy.
It is well understood that the sharing of location by a smartphone to any tracking service could pose privacy concerns <cit.>.
Some techniques try to protect privacy by adding noise <cit.> or use differential privacy <cit.> techniques to hinder inferring accurate location information.
We cannot use these techniques for crowdsourced tracking of BLE devices because the accuracy of the location is of real importance and is one of the primary goals of the service <cit.>.
We also actively hinder the ability to spoof location information by using TrustZone <cit.>.
Furthermore, work from Iasonas et al. <cit.> showed that it is possible to infer accurate location information even from noisy data.

§ CONCLUSIONS

In this work,
we first defined and formalized a set of security properties for a generic crowdsourced location tracking system.

We proposed a new design for a secure crowdsourced tracking system, .
Our design successfully prevents unauthorized attackers from taking advantage of the system to obtain sensitive information or arbitrarily control tracking devices.

In conclusion, we believe that will enable BLE tracking devices to utilize the benefits of the crowdsourced model while guaranteeing security and privacy.

§ ACKNOWLEDGEMENTS

This material is based upon work supported by the Department of
Homeland Security (DHS) (Award No. FA8750-19-2-0005) and by the Office of Naval Research (ONR) under award number N00014-17-1-2011 and N00014-20-1-2632. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and do not necessarily reflect the views of the ONR or DHS.
Part of this work is supported by the Dutch Research Council (NWO) in the context of the INTERSECT research program (NWA.1160.18.301).

§ CROWDSOURCED TRACKING SYSTEMS

tbl:crowdcommts shows the messages sent from the TApp to the corresponding TS, along with the contacted REST endpoints.

Communication mechanism used by various tracking services with the corresponding TS. The payload column indicates the relevant data used in each of the corresponding request. We use N/A to indicate that the payload is not relevant.

3*Tracking System     6c|Communication with TS
2c|Owner Registration     2c|Location Update     2c|Location Query
End Point        Payload        End Point         Payload         End Point         Payload
TrackR                                        c]@c@<https://platform.thetrackr.com/rest>
</item?usertoken=[USERTOKEN]>                          c]@c@<https://platform.thetrackr.com/rest>
</tracker/batch/secure/[DEVICETOKEN]>       c]@c@,
Location coordinates                c]@c@<https://platform.thetrackr.com/rest>
</item?usertoken=[USERTOKEN]>                           N/A
CUBE                                          c]@c@<https://net.cubetracker.com/>
<AddCubeWithMac=[MACADDRESS]   >
<type=CUBE   hardware=[HARDWARETYPE]>                      Bluetooth MAC address     c]@c@<https://net.cubetracker.com/>
<api/devices>                       c]@c@ Bluetooth MAC address,
Location coordinates                  c]@c@<https://net.cubetracker.com/>
<api/devices?emailID=[EMAILID]>                       N/A
Chipolo                                       c]@c@<https://api.chipolo.net/v2/>
<user/[USERID]/lookup/mac/[MAC ADDRESS]>

<user/[USERID]/chipolo>                      c]@c@GET Request Returns:

POST Request Payload:

<user/[DEVICEID]/chipolo/[chipoloid]>                       c]@c@ GET Request Returns:

POST Request Payload:

Location coordinates                c]@c@<https://api.chipolo.net/v2/>
<user/[USERID]/state>                       N/A
Pebblebee                                     c]@c@<https://api.pebblebee.com/v1/>
<devices/[MAC ADDRESS]>                      N/A      c]@c@<https://data.pebblebee.com/v1/>
<devices/data/batch>                       c]@c@ Bluetooth MAC address,
Location coordinates                 c]@c@<https://api.pebblebee.com/v1/>
<devices/[MAC ADDRESS]>                       N/A
Tile                                     c]@c@<https://production.tile-api.com/api/v1/>                      Encrypted      c]@c@<https://production.tile-api.com/api/v1/>                       Encrypted                c]@c@<https://production.tile-api.com/api/v1/>                       N/A


$\ell_{\lambda}(\theta,\hat{\theta})=(\hat{\theta}-\theta_{0}/\lambda)^{2}$,
where $\lambda\in\mathbb{R}_{\geq 0}$ will be adjusted below. Setting
$\boldsymbol{Q}_{t}=q_{t}$, $\hat{\boldsymbol{Q}}_{t}=\hat{q}_{t}$, we obtain
the iteration

$\displaystyle
q_{t+1}=\frac{\hat{q}_{t}}{1+\hat{q}_{t}}\,,\;\;\;\;\hat{q}_{t}=\frac{1}{\delta}\mathbb{E}\big{\\{}\mathbb{E}[\sqrt{\delta}\Theta_{0}|(\delta
q_{t})^{1/2}\Theta_{0}+G;V]^{2}\big{\\}}\ ,$ (56)

where $\Theta_{0}\sim\mu_{\theta}$,and
$V=\sqrt{\delta\tilde{\alpha}}+G^{\prime}$, $G^{\prime}\sim{\mathsf{N}}(0,1)$.
Notice that the additional factors $\sqrt{\delta}$ are due to the different
normalization of the vector $\boldsymbol{\theta}_{0}$ with respect to the
statement in Theorem 2. Also note that the second moment of the conditional
expectation bove is equal to
$\mathbb{E}\big{\\{}\mathbb{E}[\sqrt{\delta}\Theta_{0}|(\delta(q_{t}+\tilde{\alpha}))^{1/2}\Theta_{0}+G]^{2}\big{\\}}$
and a simple calculation yields

$\displaystyle\hat{q}_{t+1}=V_{\pm}(q_{t}+\tilde{\alpha})\,,\;\;\;\;q_{t}=\frac{\hat{q}_{t}}{1+\hat{q}_{t}}\,,$
(57)

which is equivalent to Eqs. (12), (13).

Let $Y=\sqrt{\delta(q_{t}+\tilde{\alpha})}\Theta_{0}+G$,
$G\sim{\mathsf{N}}(0,1)$. Theorem 2 then yields

$\displaystyle\frac{1}{p}\|\hat{\boldsymbol{\theta}}^{t}-\boldsymbol{\theta}_{0}/\lambda\|_{2}^{2}$
$\displaystyle\geq\inf_{\hat{\theta}(\,\cdot\,)}\mathbb{E}\big{\\{}\big{(}\hat{\theta}(Y)-\Theta_{0}/\lambda\big{)}^{2}\big{\\}}+o_{p}(1)$
(58)
$\displaystyle=\frac{1}{\lambda^{2}}\mathbb{E}\big{\\{}\big{(}\mathbb{E}(\Theta_{0}|Y)-\Theta_{0}\big{)}^{2}\big{\\}}+o_{p}(1)\,.$
(59)

In order to prove the upper bound (14), it is sufficient to consider
$\|\hat{\boldsymbol{\theta}}^{t}\|^{2}_{2}\leq p$. Then, for any $\lambda\geq
0$,

$\displaystyle\frac{1}{p}\langle\hat{\boldsymbol{\theta}}^{t},\boldsymbol{\theta}_{0}\rangle$
$\displaystyle\leq\frac{1}{p}\langle\hat{\boldsymbol{\theta}}^{t},\boldsymbol{\theta}_{0}\rangle-\frac{\lambda}{2p}(\|\hat{\boldsymbol{\theta}}^{t}\|^{2}_{2}-p)$
(60) $\displaystyle=\frac{\lambda}{2}+\frac{1}{2\lambda
p}\|\boldsymbol{\theta}_{0}\|_{2}^{2}-\frac{\lambda}{2p}\|\hat{\boldsymbol{\theta}}^{t}-\boldsymbol{\theta}_{0}/\lambda\|_{2}^{2}$
(61)
$\displaystyle\leq\frac{\lambda}{2}+\frac{1}{2\lambda}\mathbb{E}\\{\Theta_{0}^{2}\\}-\frac{1}{2\lambda}\mathbb{E}\big{\\{}\big{(}\mathbb{E}(\Theta_{0}|Y)-\Theta_{0}\big{)}^{2}\big{\\}}+o(1)$
(62)
$\displaystyle\leq\frac{\lambda}{2}+\frac{1}{2\lambda}V_{\pm}(q_{t}+\tilde{\alpha})+o(1)\,.$
(63)

The claim follows by choosing $\lambda=V_{\pm}(q_{t}+\tilde{\alpha})^{1/2}$,
and noting that $\|\boldsymbol{\theta}_{0}\|^{2}_{2}/p\to\mu^{2}\varepsilon$,
almost surely.

###  G.2 Proof of Corollary 2

Choose $\mu=R/\sqrt{\varepsilon}$, and let $\mu^{\prime}<\mu$,
$\varepsilon^{\prime}<\varepsilon$,
$R^{\prime}=\mu^{\prime}\sqrt{\varepsilon^{\prime}}$. Draw the coordinates of
$\boldsymbol{\theta}_{0}=\overline{\boldsymbol{\theta}}_{0}\sqrt{p}$ according
to the three points distribution with parameters
$\mu^{\prime},\varepsilon^{\prime}$. Then, with probability one, we have
$\overline{\boldsymbol{\theta}}_{0}\in\mathscrsfs{T}(\varepsilon,R)$ for all
$n$ large enough. Applying Lemma 1, we get

$\displaystyle\lim_{n\to\infty}\inf_{\overline{\boldsymbol{\theta}}_{0}\in\mathscrsfs{T}(\varepsilon,R)}\mathbb{E}\left\\{\frac{\langle\overline{\boldsymbol{\theta}}_{0},\hat{\boldsymbol{\theta}}^{t}\rangle}{\|\overline{\boldsymbol{\theta}}_{0}\|_{2}\|\hat{\boldsymbol{\theta}}^{t}\|_{2}}\right\\}\leq\sqrt{\frac{V_{\pm}(q^{\prime}_{t}+\tilde{\alpha}^{\prime})}{(\mu^{\prime})^{2}\varepsilon^{\prime}}}\,,$
(64)

ahere we used dominated convergence to pass from the limit in probability to
limit in expectation, and $q^{\prime}_{t},\tilde{\alpha}^{\prime}$ are
computed with parameters $\mu^{\prime}$, $\varepsilon^{\prime}$. By letting
$\varepsilon^{\prime}\to\varepsilon$, $\mu^{\prime}\to\mu$, and since
$\tilde{\alpha}^{\prime},q^{\prime}_{t}$ are continuous in these parameters by
an induction argument, Eq. (64) also holds with $\mu^{\prime}$,
$\varepsilon^{\prime}$, $q^{\prime}_{t}$ replaced by $\mu$, $\varepsilon$,
$q_{t}$:

$\displaystyle\lim_{n\to\infty}\inf_{\overline{\boldsymbol{\theta}}_{0}\in\mathscrsfs{T}(\varepsilon,R)}\mathbb{E}\left\\{\frac{\langle\overline{\boldsymbol{\theta}}_{0},\hat{\boldsymbol{\theta}}^{t}\rangle}{\|\overline{\boldsymbol{\theta}}_{0}\|_{2}\|\hat{\boldsymbol{\theta}}^{t}\|_{2}}\right\\}\leq\sqrt{\frac{V_{\pm}(q_{t}+\tilde{\alpha})}{\mu^{2}\varepsilon}}\,,$
(65)

Claims $(a)$ and $(b)$ follow by upper bounding the right-hand side of the
last equation.

First notice that $V_{\pm}(q)=\mu^{4}\varepsilon^{2}\delta\,q+O(q^{2})$ and
hence Eqs. (12), (13) imply that, for any $\eta>0$ there exists $q_{*}>0$ such
that, if $q_{t}+\tilde{\alpha}\leq q_{*}$, then

$\displaystyle
q_{t+1}\leq(\mu^{4}\varepsilon^{2}\delta+\eta)(q_{t}+\tilde{\alpha})\,.$ (66)

If $\mu^{4}\varepsilon^{2}\delta<1$, choosing
$\eta=(1-\mu^{4}\varepsilon^{2}\delta)/2$, this inequality implies $q_{t}\leq
2\tilde{\alpha}/(1-\mu^{4}\varepsilon^{2}\delta)$, which proves claim $(a)$.

For the second claim, we use the bounds $e^{-\delta
q\mu^{2}/2}\cosh(\mu\sqrt{\delta q}G)\geq 0$ and $x/(1+x)\leq x$ in Eq. (13)
to get $q_{t}\leq\overline{q}_{t}$ for all $t$, where $\overline{q}_{0}=0$ and

$\displaystyle\overline{q}_{t+1}$
$\displaystyle=F_{0}(\overline{q}_{t}+\tilde{\alpha})\,,\;\;\;\;\;\;\;F_{0}(q):=\frac{\mu^{2}\varepsilon^{2}}{1-\varepsilon}\sinh(\mu^{2}\delta
q)\,.$ (67)

Further Eq. (65) implies

$\displaystyle\lim_{n\to\infty}\inf_{\overline{\boldsymbol{\theta}}_{0}\in\mathscrsfs{T}(\varepsilon,R)}\mathbb{E}\left\\{\frac{\langle\overline{\boldsymbol{\theta}}_{0},\hat{\boldsymbol{\theta}}^{t}\rangle}{\|\overline{\boldsymbol{\theta}}_{0}\|_{2}\|\hat{\boldsymbol{\theta}}^{t}\|_{2}}\right\\}\leq\sqrt{\frac{\overline{q}_{t+1}}{\mu^{2}\varepsilon}}\,.$
(68)

Define $x_{t}:=\mu^{2}\delta\overline{q}_{t}$,
$a:=\mu^{4}\varepsilon^{2}\delta/(1-\varepsilon)$,
$b:=\mu^{2}\delta\tilde{\alpha}=(\delta/\varepsilon)(\alpha/(1-\alpha))$. Then
$x_{t}$ obeys the recursion

$\displaystyle x_{t+1}=a\sinh(x_{t}+b)\,.$ (69)

Since $a=R^{4}\delta/(1-\varepsilon)$, we know that $a<1/4$. Using the fact
that $\sinh(u)\leq 2u$ for $u\leq 1$, this implies $x_{t}\leq b$ for all $t$
provided $b<1/2$. Subsitiuting this bound in Eq. (68), we obtain the desired
claim.

###  G.3 Proof of Corollary 1

Consider first the case of a random vector $\boldsymbol{\theta}_{0}$ with
i.i.d. entries $\theta_{0,i}\sim\mu_{\theta}$. Define, for
$\Theta_{0}\sim\mu_{\theta}$,

$\displaystyle F_{\varepsilon}(q)$
$\displaystyle:=\mathbb{E}\big{\\{}\mathbb{E}[\Theta_{0}|\sqrt{q}\Theta_{0}+G]^{2}\big{\\}}$
(70)
$\displaystyle=e^{-q\mu^{2}}\mu^{2}\varepsilon^{2}\mathbb{E}\left\\{\frac{\sinh(\mu\sqrt{q}G)^{2}}{1-\varepsilon+\varepsilon
e^{-q\mu^{2}/2}\cosh(\mu\sqrt{q}G)}\right\\}\,.$ (71)

Setting $q_{t}=\tau_{t}^{-2}$, $\hat{q}_{t}=\sigma_{t}^{2}$, and
$\tilde{\alpha}=\alpha/(1-\alpha)$, and referring to Lemma 4, the state
evolution recursion (5) takes the form

$\displaystyle\hat{q}_{t}$
$\displaystyle=F_{\varepsilon}(q_{t}+\tilde{\alpha})\,,\;\;\;\;q_{t+1}=\delta\,H(\hat{q}_{t})\,,$
(72) $\displaystyle H(q)$
$\displaystyle:=\mathbb{E}_{G_{0},Y}\left[\left(\frac{\mathbb{E}_{G_{1}}\partial_{x}p(Y|\sqrt{q}\,G_{0}+\sqrt{1-q}G_{1})}{\mathbb{E}_{G_{1}}p(Y|\sqrt{q}\,G_{0}+\sqrt{1-q}G_{1}}\right)^{2}\right]\,.$
(73)

Notice the change in factors $\delta$ with respect to Eq. (5), which is due to
the different normalization of the design matrix.

By the same argument used in the proof of Lemma 1, Theorem 1 implies that, for
any GFOM, with output $\hat{\boldsymbol{\theta}}_{t}$, we have

$\displaystyle\lim_{n,p\to\infty}\mathbb{E}\frac{\langle\overline{\boldsymbol{\theta}}_{0},\hat{\boldsymbol{\theta}}^{t}\rangle}{\|\overline{\boldsymbol{\theta}}_{0}\|_{2}\|\hat{\boldsymbol{\theta}}^{t}\|_{2}}\leq\sqrt{\hat{q}_{t}}\,.$
(74)

We next compute the first order Taylor-expansion of the iteration (72), and
obtain $F_{\varepsilon}(q)=q+O(q^{2})$,
$H(q)=q/\delta_{\mbox{\tiny{sp}}}+O(q^{2})$ (the first order Taylor expanson
of $H(q)$ was already computed in [MM19]). As a consequence, for any $\eta>0$,
there exists $\alpha_{0}$ such that, if $\tilde{\alpha}<\alpha_{0}$,
$q_{t}<\alpha_{0}$, then

$\displaystyle
q_{t+1}\leq(\frac{\delta}{\delta_{\mbox{\tiny{sp}}}}+\eta)(q_{t}+\tilde{\alpha})\,.$

The claim follows by taking
$\eta=\eta(\delta):=(\delta_{\mbox{\tiny{sp}}}-\delta)/(2\delta_{\mbox{\tiny{sp}}})$,
whence $q_{t}\leq\tilde{\alpha}/\eta(\delta)$ for all $t$, provided
$\tilde{\alpha}<\alpha_{*}:=\alpha_{0}\eta(\delta)$. The deterministic
argument follows in the same way as Corollary 2.


to random oracle $O$, $\Omega_{\Cl_M\cup \Ser}(c, i, T, r_{\Cl_M\cup \Ser}$) outputs the message for
party $c$ in round $i$ (possibly making several queries to $O$ along
the way).  We note that $\Omega_{\Cl_M\cup \Ser}$ is thus effectively
choosing the inputs for all corrupt users.

We will define a simulator  through a series of
(polynomially many) subsequent modifications to the real
execution $\textsf{Real}_\name$, so that the views of $\Omega_{\Cl_M\cup\Ser}$ in any two subsequent executions are computationally indistinguishable.

* $\textsf{Hyb}_0$: This random variable is distributed exactly as the
view of $\Omega_{\Cl_M\cup\Ser}$ in $\textsf{Real}_{\name}$, the joint view of the parties $\Cl_M\cup\Ser$
in a real execution of the protocol.

* $\textsf{Hyb}_1$:
In this hybrid, for
any pair of honest clients $\Cl_i,\Cl_j \in \Cl_H$, the simulator changes the key from $\textsf{KA.agree}(pk_j,sk_i)$ to  a uniformly random key. We use Diffie-Hellman key exchange protocol in .
The DDH assumption [32]  guarantees that this hybrid is indistinguishable from the previous one.
also be able to break the DDH.

* $\textsf{Hyb}_2$: This hybrid is identical to $\textsf{Hyb}_1$
, except additionally,  will abort if $\Omega_{\Cl_M\cup \Ser}$ succeeds to deliver, in
round 2, a message to an honest client $\Cl_i$
on behalf of another honest client $\Cl_j$, such that $(1)$ the
message is different from that of  $\textsf{Sim}$, and $(2)$ the message does
not cause the decryption  to fail. Such a message would directly
violate the IND-CCA security
of the encryption scheme.

* $\textsf{Hyb}_3$: In this round, for every honest party in $\Cl_H$,  samples $s_i\in \Fl$ such that $\Vl(s_i)=1$ and replaces all the shares and the check strings accordingly. This allows the server to compute the $\sigma_i=(w^{out}_i,\lambda_i)$ such that $w^{out}_i=1 \wedge \lambda_i=0$  for all honest clients in the same way as in the previous hybrid. An adversary noticing any difference would break $(1)$ the computational discrete logarithm assumption used by the VSS [35], OR  $(2)$ the  guarantee of the encryption scheme, OR $(3)$ the information theoretic perfect secrecy of Shamir's secret sharing scheme with threshold $m+1$,  OR $(4)$ zero-knowledge property of SNIP.

* $\textsf{Hyb}_4$: In this hybrid,  uses $\Ul_H$ to compute the following polynomial. Let $(j,S_j)$ represent the share of $\sum_{i\in \Cl_H}{s_i}$ for a malicious client $\Cl_j\in\Cl\setminus\Cl_H$ where $s_i$ denotes the random input  had sampled for $\Cl_i\in \Cl_H$ in $\textsf{Hyb}_3$.  performs polynomial interpolation to find the $m+1$-degree polynomial $p*$ that satisfies  $p*(0)=\Ul_H$ and $p(j)=S_j$. Next, for all honest client,  computes the share for $\Ul=\Ul_H+\sum_{\Cl_j\in\bar{C}}u_j$ (Eq. <ref>) by using the polynomial $p*$ and the relevant messages from $\Omega_{\Cl_M\cup\Ser}$. Clearly, this hybrid is indistinguishable from the previous one by the perfect secrecy of Shamir's secret shares. This concludes our proof.

§.§ Additional Evaluation Results

In this section, we provide some additional evaluation results on model accuracy in Fig. <ref>. We use the same configuration as the one reported in Sec. <ref>. Our observations are in line with our discussion in Sec. <ref>.

§.§ Discussion Cntd.

Here, we present additional avenues of future work for .

Revealing Malicious Clients. In our current implementation,  publishes the (partial) list of malicious clients $\CA$.

To hide the identity of malicious clients, we could include an equal number of honest clients in the list before publishing it, thereby providing those clients plausible deniability.
We leave more advanced cryptographic solutions as a future direction.

MNIST: Scaling attack with norm bound validation predicate.

FMNIST: Scaling attack with norm bound validation predicate.

FMNIST: Min-Sum attack with cosine similarity validation predicate.

EMNIST: Additive noise attack with Zeno++ similarity validation predicate.

EMNIST: Scaling attack with cosine similarity validation predicate.

EMNIST: Sign flip attack with norm ball validation predicate.

CIFAR-10: Min-Max attack with Zeno++ validation predicate.

CIFAR-10: Scaling attack with norm bound validation predicate

CIFAR-10: Sign flip attack with norm ball validation predicate.

Accuracy analysis of  continued. Test accuracy is shown as a function of the FL iteration for different datasets and attacks.

Private Validation Predicate.  If $\Vl(\cdot)$ contains some secrets of the server $\Ser$, we can employ multiple servers where the computation of $\Vl(u)$ is done at the servers [28]. We leave a single-server solution of this problem for future work.

Byzantine-Robust Aggregation. In , the integrity check is done individually on each client update, independent of all other clients.
An alternative approach to compare the  local
model updates of all the clients (via pairwise distance/ cosine similarity)  [14, 15, 24, 34, 33] and remove statistical outliers before using
them to update the global model. A general framework to support secure Byzantine-robust aggregations rules, such as above, is an interesting future direction.

0.9$\Vl(\cdot)$ Structure. If 0.9$\Vl(\cdot)$ contains repeated structures, the $G$-gate technique [19] can improve efficiency.

Complex Aggregation Rules.
can be used for more complex aggregation rules, such as mode,  by extending SNIP with affine-aggregatable encodings (AFE) [28].

Differential Privacy. The privacy guarantees of  can be enhanced by using differential privacy (DP) to reveal a noisy aggregate using techniques such as [44]. Adding DP would also provide additional robustness guarantees [84, 64].

Scaling . Our experimental results in Sec. <ref> show that  has reasonable performance for clients sizes up to $250$. One way of scaling  for larger client sizes can be by dividing the clients into smaller subsets of size $\sim250$ and then running  for each of these subsets [16].

Towards poly-logarithmic complexity. Currently,  dominant term in the complexity is $O(mnd)$ which results in a $O(n^2)$ dependence on $n$ (since we consider $m$ is a fraction of $n$). This can be reduced to $O(n\log^2 nd)$ by using the techniques from [9].  Specifically, instead of having each client verify the proofs of all others (complete graph for the verification) we can follow the exact construction of the $k$-regular graph $G$ from [9] such that $k=O(\log n$) and only neighbors in $G$ act as verifiers for each other. The exact steps are as follows:
* Each client $C_i$ generates $n$ shares. It sends the corresponding shares to its $k$-neighbors (according to graph G from [9])  and the verification can be done on them as described currently in . Note that these shares follow a $t$-out-of-$n$ scheme where $t<k$.

* $C_i$ encrypts the shares for the non-neighbors using a threshold (denoted by $t_{enc}$) fully homomorphic encryption scheme such as BGV [22] (the threshold variant can be obtained using work such as [42, 20]). Note that this threshold, $t_{enc}>m$ is different from that of the secret shares. This encryption is necessary for ensuring data privacy since for the threshold of the shares we could have $t<m$.

* For the aggregation step, first the clients check the validity of the shares of its non-neighbors  (this can be done via homomorphic multiplications as shown by Feldman [35]). Next, only the shares corresponding to the clients that (i) pass the first step of input verification,  and (ii) have valid shares, are aggregated. Note that the shares corresponding to neighbors (for verification) can be encrypted using the public key of the encryption scheme for this step.

* Each client now has the ciphertext of its share of the aggregate (corresponding to $(i,U_{i})$ where $U_{i}=\sum_{C_j\in C\setminus C*}u_{ji}$ in the current EIFFeL protocol) which is sent to the server. The server performs the reconstruction directly on these ciphertexts (using their homomorphic property) and obtains the ciphertext of the final aggregate. This can then be decrypted with the help of the clients to obtain the final aggregate in the clear.

§.§ SNIP

A SNIP protocol comprises two main stages:

1) Generation of Proof. For generating the proof, the prover $\Pro$ first evaluates the
circuit $\V$ on their input $x$ to obtain the value of every wire in the arithmetic circuit corresponding to the computation of $\Vl(x)$.  Using these wire values, $\Pro$  constructs
three polynomials $f$, $g$, and $h$, which encode the values on
the input and output wires of each of the $M$ multiplication
gates in the $\Vl(x)$ computation.
To do so, the multiplication gates are topologically ordered from input to output nodes. Polynomials $f$ and $g$ are then defined to
be the lowest-degree polynomials for which: (1) $f(0)$ and $g(0)$ are chosen at random, and (2) $f(j) = y_j$ and
$g(j) = z_j, \forall j \in [\Ml]$, where $y_j$ and $z_j$ are the values of the two input wires of the $j$-th multiplication gate. Next, polynomial $h$ is the defined to be the product polynomial, $h = f \cdot g$.
By construction, the degree of polynomials $f$ and $g$ is at most $M-1$, and the polynomial $h$ has degree at most $2M - 2$. Importantly, $\forall j \in [\Ml]: h(j)$ gives the values of the output wire of the $j$-th multiplication gate in the $\Vl(x)$ circuit because $h(j) = f(j) \cdot g(j) = y_j\cdot z_j$.
The prover $\Pro$ uses polynomial interpolation to construct $f$ and $g$, and multiplies them to obtain $h=f\cdot g$. The prover also samples a single set of Beaver's multiplication triples [7]: $(a,b,c)\in \Fl^3$ such that $a\cdot b = c \in \Fl$. Finally, it generates the shares of the proof string, $[\pi]_i =\langle ([a]_i,[b]_i,[c]_i), [h]_i\rangle$, which consists of:

* shares of the coefficients of the polynomial $h$, denoted by $[h]_i$, and
* shares of the  Beaver's multiplication triples, $([a]_i,[b]_i,[c]_i)\in \Fl^3$. The prover then sends the respective shares of the input, $x$, and the proof  $( [x]_i, [\pi]_{i})$ to each of the verifiers $\Ver_i$.

2) Verification of Proof. To verify that $\Vl(x)=1$ and hence accept the private input $x$, the verifiers need to check two things:
* check that the value of final output wire of the computation, $\Vl(x)$, denoted by $w^{out}$ is indeed $1$, and
* check the consistency of the $\Pro$'s computation of $\Vl(x)$. To this end, each verifier $\Ver_i$ locally constructs the shares of every wire in $\Vl(x)$. This can be done via affine operations on the shares of the private input $[x]_i$ and $[h]_i$ (see App. <ref> for details). Next, $\Ver_i$ broadcasts a summarized message $\sigma=([w^{out}]_i,[\lambda]_i)$, where $[w^{out}]_i$ is $\Ver_i$'s share of the output wire and $[\lambda]_i$ is a share of a random digest that the verifier computes from the shares of the other wire values and the proof string $\pi_i$. Using these broadcasted messages, the verifiers check the proof as follows:

* For checking the output wire, the verifiers can reconstruct its exact value from all the broadcasted shares $w^{out}=\sum_{i=1}^k [w^{out}]_i$ and check that $w^{out}=1$.
* The circuit consistency check is more involved and is performed using the random digest $\lambda$. First, $\Ver_i$ locally computes the shares of the polynomials $f$ and $g$ (denoted as $[f]_i$ and $[g]_i$) from its shares of the wire values of $\Vl(x)$ (see  App.<ref> for details). To verify the circuit consistency, the verifiers need to check that the shares  $[h]_i$ sent by the prover $\Pro$ are of the correct polynomial, that is, confirm that $f\cdot g =h$. For this, SNIP uses the classic Schwartz-Zippel randomized polynomial identity test [74, 98]. Specifically, a verifier chooses a random $r\in \Fl$ and tests whether $\lambda=f(r) \cdot g(r)-h(r)=0$.  For computing the random digest $\lambda$, every verifier $\Ver_i$ first computes the shares $[f(r)]_i], [g(r)]_i$ and $[h(r)]_i$ locally using affine operations. Next, the verifiers generate the share of the product term $[f(r)\cdot g(r)]_i$ and subsequently $[\lambda]_i=[f(r) \cdot g(r)-h(r)]_i$ using the shares of the Beaver's multiplication triples $([a]_i,][b]_i,[c]_i)$. This multiplication requires one round of communication between the verifiers. The exact details of this step are not critical for understanding the protocol but we include them for reference  in App. <ref>. SNIP Deployment Scenario. SNIP is optimized for the client-server setting. It was originally proposed in the context of a multi-server deployment scenario, named Prio, where a client's  private input is secret-shared among the servers. The client acts as the prover and the servers act as the verifiers.

In addition to the above cryptographic primitives,  uses two system building blocks.