# Privacy Enhancement on Unilateral Bluetooth Authentication Protocol for Mobile Crowdsensing

Authors: Da-Zhi Sun; Ji-Dong Zhong
Journal: Security and Communication Networks
 (2021)

---

## Abstract

As an open standard for the short-range radio frequency communications, Bluetooth is suitable for Mobile Crowdsensing Systems (MCS). However, the massive deployment of personal Bluetooth-enabled devices also raises privacy concerns on their wielders. Hence, we investigate the privacy of the unilateral authentication protocol according to the recent Bluetooth standard v5.2. The contributions of the paper are twofold. (1) We demonstrate that the unilateral authentication protocol suffers from privacy weakness. That is, the attacker is able to identify the target Bluetooth-enabled device once he observed the device’s previous transmitted messages during the protocol run. More importantly, we analyze the privacy threat of the Bluetooth MCS, when the attacker exploits the proposed privacy weakness under the typical Internet of Things (IoT) scenarios. (2) An improved unilateral authentication protocol is therefore devised to repair the weakness. Under our formal privacy model, the improved protocol provably solves the traceability problem of the original protocol in the Bluetooth standard. Additionally, the improved protocol can be easily adapted to the Bluetooth standards because it merely employs the basic cryptographic components available in the standard specifications. In addition, we also suggest and evaluate two countermeasures, which do not need to modify the original protocol.


---

## Body

## 1. Introduction

Bluetooth [1] is an open technology standard for wireless short-range radio frequency communications. Bluetooth hardware and software modules are already integrated into many kinds of consumer and business devices including smart phones, headsets, laptops, keyboards, mouses, tablets, and automobiles. Actually, Bluetooth offers a highly practical approach to establishing Mobile Crowdsensing Systems (MCS) because of its universality, convenience, and adaptation.In order to protect device users and their sensitive data, Bluetooth provides a security solution for the hostile environments [2]. More precisely, the effective Bluetooth standard specifications [3–5] define four security modes, namely, modes 1 through 4. Each Bluetooth-enabled device must operate in one of the four security modes. Security mode 1 does not employ any security measure. Security modes 2 and 4 are treated as the service level-enforced security modes. That is to say, the device in security mode 2 or 4 will not start any security procedure until it receives or initiates a channel establishment request. Security mode 3 is the link level-enforced security mode, where the security procedures are initiated before the physical link is fully established. Security modes 2, 3, and 4 are all composed of three crucial procedures, i.e., pairing and link key generation, authentication, and confidentiality. It needs to be pointed out that the authentication procedure and the confidentiality procedure in security modes 2, 3, and 4 are fully the same. We briefly review the three procedures as follows:Pairing and link key generation: this procedure is responsible for establishing the link key between a pair of the devices and further binding the trusted devices. The link key will be used throughout the subsequent security procedures. Security modes 2 and 3 employ the same pairing and link key generation scheme called Personal Identification Number (PIN) pairing. The PIN pairing is analyzed and improved in the literature such as [6, 7]. However, in security mode 4, Secure Simple Pairing (SSP) is used instead. A series of works such as [8–11] address the security properties of SSP under the distinctive practical concerns.Authentication: this procedure applies to two paired devices and needs their shared link key generated by the previous procedure. The procedure goal is to validate the legitimate identity claimed by the pairing device itself. When the authentication attempt fails, any retry with the same identity will be delayed for a waiting interval.Confidentiality: this procedure provides a separate confidential service to the data transmitted between the pairing devices.The widespread use of Bluetooth-enabled devices has given birth to many wireless personal applications, such as connecting mobile phones to wireless headsets, emergency systems of cars, and digital wallets and merchants. Bluetooth is often used for establishing Wireless Personal Area Network (WPAN) because of its usability and performance. In fact, the Bluetooth standard is adapted in IEEE 802.15 [12] for WPAN. Obviously, it is important to protect the privacy of the users under Bluetooth WPAN. However, the absence of physical contact during communications and the expected ubiquity of sensitive applications (such as the MCS [13, 14]) will encourage nefarious entities to observe and track the devices through their transmitted Bluetooth messages. In a Bluetooth WPAN application, the attacker may intercept and analyze the transmitted messages among devices. If at this time a device is linked to a user, the identity of the user will then be disclosed by his device. Figure 1 illustrates a Bluetooth application scenario where the attacker intercepts and analyzes the transmitted messages among devices. Hence, the need for Bluetooth to be resistant against the privacy threats arises. To guarantee the privacy of the user, the transmitted messages of the security mode in particular should not be exploited to identify the target device.Figure 1
Interception of personal Bluetooth communication.The National Institute of Standards and Technology (NIST) [15] surveyed the privacy features and threats according to the early versions of the Bluetooth standard. A few of works [16–18] showed that the privacy of a particular user can be compromised if the Bluetooth-enabled device address associated with the user is captured, and therefore proposed the improved schemes to repair it. Moreover, some devices [19, 20] have been implemented with the protection mechanisms for their Bluetooth addresses. Many researchers [21–25] found that the public advertising channels in Bluetooth Low Energy (BLE) may leak the identity information of the device and therefore designed the privacy countermeasures. Celosia and Cunche [26] reported a timing attack, which can be triggered by a remote attacker, to infer the state of a device from Bluetooth information and undermine the privacy of the user. As a potential privacy threat, Bluetooth traffic can be sniffed even if the device is in indiscoverable mode, as demonstrated by Albazrqaoe et al. [27]. Bello-Ogunu et al. [28] developed a privacy management framework that provides a policy configuration platform for BLE beacon. We [29] addressed the privacy vulnerability of SSP’s BLE version in security mode 4. In addition, Bluetooth systems [30–32] in the application level are designed to protect the privacy of the user. Due to the fast development of Bluetooth WPAN and its integration into Internet of Things (IoT), more and more privacy protection features are now already included in the Bluetooth standard specifications [4].To the best of our knowledge, there is still no active research on the privacy of the authentication procedure in the Bluetooth security solution. However, the attacker may exploit the vulnerabilities in the authentication procedure to compromise the privacy of the user, especially when the Bluetooth-enabled devices are deployed in the IoT environment. Moreover, the overall strength of privacy protection would be dominated by the weakest procedure in the Bluetooth security solution. Hence, we focus on the privacy enhancement of the authentication procedure according to the recent Bluetooth standard v5.2 [4].Two challenge-response protocols, i.e., the unilateral (or legacy) authentication protocol and the mutual (or secure) authentication protocol, are used to realize the authentication procedure in the Bluetooth standard v5.2. In this paper, we will systematically investigate the privacy of the unilateral authentication protocol. We demonstrate that the attacker can track the target Bluetooth-enabled device once he observed the device’s previous transmitted messages during the protocol run. We further evaluate its impact on the Bluetooth MCS, when our proposed privacy weakness is exploited under typical IoT scenarios. An improved unilateral authentication protocol is therefore proposed to overcome the privacy weakness in the original protocol. Without high extra implementation costs, our improved protocol provably solves the traceability problem in the original protocol. In addition, two non-protocol countermeasures are also suggested and evaluated for the privacy enhancement.


## 2. Review of Unilateral Bluetooth Authentication Protocol

In the unilateral authentication protocol [4], each Bluetooth-enabled device is referred to as either the claimant or the verifier. The claimant is a device manifesting its own identity to the verifier, and the verifier is a device validating the identity of the claimant. The protocol validates the devices by verifying the knowledge of the shared link key, which is established in the pairing and link key generation procedure. The protocol makes use of a cryptographic hash algorithm E1 with an output of 128 bits. The algorithm E1 is based on the SAFER + block cipher but with some minor modifications [4]. Let KLINK be the shared link key between the claimant and the verifier. Let BD_ADDR be the claimant’s device address. The protocol is shown as Figure 2, and the authentication session is described as follows.Step 1: the verifier generates a 128-bit random number AU_RAND as the challenge and then sends it to the claimant.Step 2: both devices calculate the authentication token {SRES, ACO} =E1 (KLINK, BD_ADDR, AU_RAND), where SRES known as the signed response is the 32 most significant bits of the 128-bit output of the algorithm E1, and ACO known as authenticated ciphering offset is the remaining bits for creating the encryption key in the confidentiality procedure.Step 3: the authentication response SRES is sent from the claimant to the verifier.Step 4: the verifier compares the received SRES with the counterpart calculated locally. If they are the same, the protocol run succeeds and the verifier accepts the identity of the claimant; otherwise, the protocol run fails.Figure 2
Bluetooth authentication protocol.The link key is either semi-permanent or temporary according to Bluetooth standard specifications [4]. A semi-permanent link key may be still used after the current secure session is terminated. This implies that a semi-permanent link key may be activated in the authentication of several subsequent connections between the devices. The lifetime of a temporary link key is limited by the lifetime of the current secure session; that is, it shall not be reused in a later secure session. In brief, a link key will remain valid until the next successful run of the pairing and link key generation procedure.


## 3. Privacy Weakness of Unilateral Bluetooth Authentication Protocol

Assume that the attacker eavesdrops and records AU_RAND and SRES during a protocol run between the claimant (Device 1) and the verifier (Device 2). Herein, this assumption is reasonable because AU_RAND and SRES are insecurely transmitted over a Bluetooth wireless channel. As shown in Figure3, the attacker can use the past AU_RAND and SRES to validate whether the claimant is Device 1 or not by the following steps.Step 1: replay the recorded AU_RAND in Step 1 of the unilateral authentication protocol.Step 2: omit Step 2 of the unilateral authentication protocol.Step 3: upon receiving the claimant’s SRES in Step 3 of the unilateral authentication protocol, compare it with the recorded SRES. If they are equal, the claimant is Device 1.Figure 3
Bluetooth-enabled device tracing by authentication process.If the claimant is Device 1, the same BD_ADDR, AU_RAND, andKLINK should be used as the input of algorithm E1 during the attacker’s authentication run. Hence, the algorithm E1 will output the same SRES as the attacker’s recorded one. On the contrary, if the claimant is not Device 1, the different KLINK and BD_ADDR should be used as the input of the algorithm E1. In this case, the algorithm E1 will output the same SRES as the previous recorded one with a negligible probability. Hence, the attacker can always use the proposed attack to identify Device 1. We further discuss the proposed attack as follows.To prevent the proposed attack, the device can update itsKLINK before each authentication session. However, we argue that it is an impractical method due to the heavy overheads of the pairing and link key generation procedure.IfKLINK and BD_ADDR are available, the attacker is also able to identify the device by the authentication session. However, this implies that the attacker must be powerful enough to break into the device. In practice, it is hard for the attacker to directly crack a device.The proposed attack merely exploits the vulnerabilities in the unilateral authentication protocol of the Bluetooth standard. Moreover, since security modes 2, 3, and 4 all employ this protocol, the proposed attack is regarded as a broad-spectrum tracking method.In addition, it is worth noting that the Bluetooth standard specifications [4] give a countermeasure to prevent the attacker from repeating the authentication procedure. That is, “when the authentication attempt fails, a waiting interval shall pass before the verifier will initiate a new authentication attempt to the same claimant, or before it will respond to an authentication attempt initiated by a device claiming the same identity as the failed device. For each subsequent authentication failure, the waiting interval shall be increased exponentially. For example, after each failure, the waiting interval before a new attempt can be made could be twice as long as the waiting interval prior to the previous attempt. The waiting interval shall be limited to a maximum.”However, this countermeasure cannot overcome the proposed privacy weakness on the unilateral authentication protocol because the attacker merely uses one authentication attempt to confirm the identity of the claimant.


## 4. Privacy Threat Analysis of Bluetooth MCS due to Proposed Weakness

In some Bluetooth applications such as [9, 11], the privacy of the user is not a serious concern. However, when the Bluetooth devices enter into the MCS, we must take user privacy very seriously because a large amount of personal sensitive data may be collected automatically. In this section, we use the proposed privacy weakness to analyze the privacy threat of the Bluetooth MCS under several typical IoT scenarios.We know that MCS architecture always consists of three tiers, i.e., the devices, the edge gateway, and the cloud. The devices include networked sensors, actuators, and embedded communication hardware, which adopt the widely used standards such as Bluetooth and Zigbee.


### 4.1. Bluetooth IoT Scenarios

Since the standard v4.2 [33], the Bluetooth group begins to promote the IoT technology. With the fast development of the IoT applications, many MCS designs are proposed by using Bluetooth-enabled devices and their networks. For example, the MCS architecture under the Bluetooth IoT [34] can be divided into six layers: hardware layer, microcontroller layer, Bluetooth connectivity layer, connectivity layer, Bluetooth IoT cloud stack layer, and application layer. We can enumerate several typical Bluetooth IoT scenarios as follows.


#### 4.1.1. Child Care

In this scenario such as [35], children wear wristbands with Bluetooth-enabled devices, and the Bluetooth network would provide the nursery teachers with information on whether the children are still within reach. Furthermore, the nursery administrators could get statistics of the total daily children movement information from their Bluetooth-enabled devices.


#### 4.1.2. Medical and Healthcare

Bluetooth-enabled health monitoring devices [36] can be deployed to realize remote health monitoring and emergency notification systems. These devices can range from blood pressure and heart rate monitors to advanced devices capable of monitoring specialized implants. Furthermore, if the hospital beds are equipped with Bluetooth-enabled devices, the doctor can detect whether the hospital bed is occupied or when a patient is attempting to get up.


#### 4.1.3. Animal Tracker

By mounting the relay nodes around the pastures, farmers can monitor the livestock with Bluetooth-enabled devices and keep track of each individual animal of the herd. Moreover, with the Bluetooth data of the livestock, the precision feed mechanisms can be implemented with using artificial intelligence to count the number of the livestock, analyze the health trend of the livestock, and evaluate the breeding effectiveness.


#### 4.1.4. Barcode Scanner

Bluetooth IoT is suitable for barcode scanner applications, since Bluetooth network could cover a large warehouse or even multiple large warehouses potentially with a lot of obstacles and walls. Each warehouse worker may use his own barcode scanner with the constant Bluetooth network coverage.


#### 4.1.5. Greenhouse Monitoring System

Bluetooth-enabled devices could collect plant data on temperature, rainfall, humidity, wind speed, pest infestation, and soil content and further communicate with sprinkler and ventilation systems. The user could manually control and configure systems of the greenhouse with an app using smart phone as a Bluetooth controller. This greenhouse facility could easily be expanded by adding more and more nodes when necessary.


#### 4.1.6. Battlefield Surveillance

Soldiers and military equipment with the wireless network access (called the node) could search the objects for probably hostile forces. Then, they provide the real-time situational awareness to the base station which in turn sends over those data to other nodes as well as to the command center. It is high time that the military may tend to use commercial off-the-shelf Bluetooth sensors due to their inherent price advantages.


### 4.2. Proposed Weakness for Bluetooth MCS

Here, we show that the proposed attack endangers the privacy of the device owner and further poses a threat to the privacy of the Bluetooth MCS.The sophisticated attacker sends his owner AU_RANDs to the target devices and records their corresponding SRESs. He also collects the target devices’ AU_RANDs and SRESs over the Bluetooth channel. These values can be stored in a data table as shown in Figure4. The attacker may remove AU_RAND and SRES from the data table, if their corresponding KLINK expires. He simultaneously attempts to initiate the authentication runs with all potential devices within the reach of the imitative device under his control. If any device responds to the right SRES, the corresponding identity linkage will be disclosed to the attacker. With supplementary information such as locations, times, user behavior, and known identities, the attacker can deduce the user identities of the target devices and compromise the privacy of the Bluetooth MCS.Figure 4
Multiple-device tracking table.For example, consider the child care scenario in Section4.1. The proposed privacy weakness can be exploited to track how a victim child’s Bluetooth-enabled device within some area moves. This helps the attacker to infer the child’s movement characteristics. What is more important, the attacker can derive the relationship among children via a great deal of the tracked Bluetooth-enabled devices.


### 4.3. Privacy Threat of Bluetooth MCS

We now analyze the privacy threat of the MCS under the IoT scenarios in Section4.1, when the attacker exploits the proposed privacy weakness. In Table 1, we first collect and analyze the privacy features of the MCS on three criteria: the correlation between the device and the user identity, the system deployment range, and the domain’s privacy demands. Then, we can comprehensively evaluate the privacy features of the MCS and the proposed privacy weakness discussed in Section 4.2. Finally, we deduce the privacy threat level as in Table 2.Table 1
Privacy features of Bluetooth IoT scenarios.
Feature/scenarioChild careMedical and healthcareAnimal trackerBarcode scannerGreenhouse monitoring systemBattlefield surveillanceSystems based on device implantsNoPossiblePossibleNoPossiblePossibleDevice associated with a personYesPossibleNoPossibleNoPossibleFixed link between device and identityYesYesYesPossiblePossiblePossibleSystem operating locally within a restricted areaYesYesNoYesNoNoSystem within a single organizationNoNoYesNoNoYesSystem operating across different organizationsNoNoNoNoYesNoPrivacy demandHighHighLowMediumLowHighTable 2
Privacy threat incurring by proposed weakness.
Child careMedical and healthcareAnimal trackerBarcode scannerGreenhouse monitoring systemBattlefield surveillancePrivacy threat levelHighHighLowMediumLowHigh


## 4.1. Bluetooth IoT Scenarios

Since the standard v4.2 [33], the Bluetooth group begins to promote the IoT technology. With the fast development of the IoT applications, many MCS designs are proposed by using Bluetooth-enabled devices and their networks. For example, the MCS architecture under the Bluetooth IoT [34] can be divided into six layers: hardware layer, microcontroller layer, Bluetooth connectivity layer, connectivity layer, Bluetooth IoT cloud stack layer, and application layer. We can enumerate several typical Bluetooth IoT scenarios as follows.


### 4.1.1. Child Care

In this scenario such as [35], children wear wristbands with Bluetooth-enabled devices, and the Bluetooth network would provide the nursery teachers with information on whether the children are still within reach. Furthermore, the nursery administrators could get statistics of the total daily children movement information from their Bluetooth-enabled devices.


### 4.1.2. Medical and Healthcare

Bluetooth-enabled health monitoring devices [36] can be deployed to realize remote health monitoring and emergency notification systems. These devices can range from blood pressure and heart rate monitors to advanced devices capable of monitoring specialized implants. Furthermore, if the hospital beds are equipped with Bluetooth-enabled devices, the doctor can detect whether the hospital bed is occupied or when a patient is attempting to get up.


### 4.1.3. Animal Tracker

By mounting the relay nodes around the pastures, farmers can monitor the livestock with Bluetooth-enabled devices and keep track of each individual animal of the herd. Moreover, with the Bluetooth data of the livestock, the precision feed mechanisms can be implemented with using artificial intelligence to count the number of the livestock, analyze the health trend of the livestock, and evaluate the breeding effectiveness.


### 4.1.4. Barcode Scanner

Bluetooth IoT is suitable for barcode scanner applications, since Bluetooth network could cover a large warehouse or even multiple large warehouses potentially with a lot of obstacles and walls. Each warehouse worker may use his own barcode scanner with the constant Bluetooth network coverage.


### 4.1.5. Greenhouse Monitoring System

Bluetooth-enabled devices could collect plant data on temperature, rainfall, humidity, wind speed, pest infestation, and soil content and further communicate with sprinkler and ventilation systems. The user could manually control and configure systems of the greenhouse with an app using smart phone as a Bluetooth controller. This greenhouse facility could easily be expanded by adding more and more nodes when necessary.


### 4.1.6. Battlefield Surveillance

Soldiers and military equipment with the wireless network access (called the node) could search the objects for probably hostile forces. Then, they provide the real-time situational awareness to the base station which in turn sends over those data to other nodes as well as to the command center. It is high time that the military may tend to use commercial off-the-shelf Bluetooth sensors due to their inherent price advantages.


## 4.1.1. Child Care

In this scenario such as [35], children wear wristbands with Bluetooth-enabled devices, and the Bluetooth network would provide the nursery teachers with information on whether the children are still within reach. Furthermore, the nursery administrators could get statistics of the total daily children movement information from their Bluetooth-enabled devices.


## 4.1.2. Medical and Healthcare

Bluetooth-enabled health monitoring devices [36] can be deployed to realize remote health monitoring and emergency notification systems. These devices can range from blood pressure and heart rate monitors to advanced devices capable of monitoring specialized implants. Furthermore, if the hospital beds are equipped with Bluetooth-enabled devices, the doctor can detect whether the hospital bed is occupied or when a patient is attempting to get up.


## 4.1.3. Animal Tracker

By mounting the relay nodes around the pastures, farmers can monitor the livestock with Bluetooth-enabled devices and keep track of each individual animal of the herd. Moreover, with the Bluetooth data of the livestock, the precision feed mechanisms can be implemented with using artificial intelligence to count the number of the livestock, analyze the health trend of the livestock, and evaluate the breeding effectiveness.


## 4.1.4. Barcode Scanner

Bluetooth IoT is suitable for barcode scanner applications, since Bluetooth network could cover a large warehouse or even multiple large warehouses potentially with a lot of obstacles and walls. Each warehouse worker may use his own barcode scanner with the constant Bluetooth network coverage.


## 4.1.5. Greenhouse Monitoring System

Bluetooth-enabled devices could collect plant data on temperature, rainfall, humidity, wind speed, pest infestation, and soil content and further communicate with sprinkler and ventilation systems. The user could manually control and configure systems of the greenhouse with an app using smart phone as a Bluetooth controller. This greenhouse facility could easily be expanded by adding more and more nodes when necessary.


## 4.1.6. Battlefield Surveillance

Soldiers and military equipment with the wireless network access (called the node) could search the objects for probably hostile forces. Then, they provide the real-time situational awareness to the base station which in turn sends over those data to other nodes as well as to the command center. It is high time that the military may tend to use commercial off-the-shelf Bluetooth sensors due to their inherent price advantages.


## 4.2. Proposed Weakness for Bluetooth MCS

Here, we show that the proposed attack endangers the privacy of the device owner and further poses a threat to the privacy of the Bluetooth MCS.The sophisticated attacker sends his owner AU_RANDs to the target devices and records their corresponding SRESs. He also collects the target devices’ AU_RANDs and SRESs over the Bluetooth channel. These values can be stored in a data table as shown in Figure4. The attacker may remove AU_RAND and SRES from the data table, if their corresponding KLINK expires. He simultaneously attempts to initiate the authentication runs with all potential devices within the reach of the imitative device under his control. If any device responds to the right SRES, the corresponding identity linkage will be disclosed to the attacker. With supplementary information such as locations, times, user behavior, and known identities, the attacker can deduce the user identities of the target devices and compromise the privacy of the Bluetooth MCS.Figure 4
Multiple-device tracking table.For example, consider the child care scenario in Section4.1. The proposed privacy weakness can be exploited to track how a victim child’s Bluetooth-enabled device within some area moves. This helps the attacker to infer the child’s movement characteristics. What is more important, the attacker can derive the relationship among children via a great deal of the tracked Bluetooth-enabled devices.


## 4.3. Privacy Threat of Bluetooth MCS

We now analyze the privacy threat of the MCS under the IoT scenarios in Section4.1, when the attacker exploits the proposed privacy weakness. In Table 1, we first collect and analyze the privacy features of the MCS on three criteria: the correlation between the device and the user identity, the system deployment range, and the domain’s privacy demands. Then, we can comprehensively evaluate the privacy features of the MCS and the proposed privacy weakness discussed in Section 4.2. Finally, we deduce the privacy threat level as in Table 2.Table 1
Privacy features of Bluetooth IoT scenarios.
Feature/scenarioChild careMedical and healthcareAnimal trackerBarcode scannerGreenhouse monitoring systemBattlefield surveillanceSystems based on device implantsNoPossiblePossibleNoPossiblePossibleDevice associated with a personYesPossibleNoPossibleNoPossibleFixed link between device and identityYesYesYesPossiblePossiblePossibleSystem operating locally within a restricted areaYesYesNoYesNoNoSystem within a single organizationNoNoYesNoNoYesSystem operating across different organizationsNoNoNoNoYesNoPrivacy demandHighHighLowMediumLowHighTable 2
Privacy threat incurring by proposed weakness.
Child careMedical and healthcareAnimal trackerBarcode scannerGreenhouse monitoring systemBattlefield surveillancePrivacy threat levelHighHighLowMediumLowHigh


## 5. Improved Unilateral Bluetooth Authentication Protocol

In this section, we improve the unilateral authentication protocol to prevent the proposed privacy weakness. To be compatible with the standard, the improvement should be built by the same cryptographic components as in the original unilateral authentication protocol.


### 5.1. Protocol Description

As shown in Figure5, we propose an improved protocol to repair the traceability weakness in the original protocol. The authentication session is now as follows.Step 1: the verifier generates a random number AU_RANDV as the challenge and then sends it to the claimant.Step 2: the claimant creates another random number AU_RANDC and calculates the authentication token {SRES, ACO} = E1 (KLINK, BD_ADDR, AU_RANDV, AU_RANDC). Herein, based on the SAFER + block cipher, it is necessary for the cryptographic hash algorithm E1 to have an input with a larger size. Alternatively, both AU_RANDV and AU_RANDC can be set to 64 bits, and the algorithm E1 remains the same.Step 3: the claimant sends the response AU_RANDC and SRES to the verifier.Step 4: upon receiving AU_RANDC and SRES, the verifier first uses AU_RANDC to calculate the authentication token {SRES, ACO} = E1 (KLINK, BD_ADDR, AU_RANDV, AU_RANDC). Then, it compares the received SRES with the counterpart calculated locally. If they are the same, the protocol run is successful and the verifier accepts the identity of the claimant; otherwise, the protocol run fails.Figure 5
Improved Bluetooth unilateral authentication protocol.Remark 1.
In practice, we can employ a non-symmetric split strategy for the random numbers AU_RANDV and AU_RANDC. If the risk of the tracking devices is low in some applications, the claimant’s AU_RANDC can be shortened to 32 bits or about, while keeping the length of the verifier’s AU_RANDV longer to ensure that the actual authentication strength is not degraded.The random number AU_RANDC can also be replaced with a sequence number, which never repeats in each protocol run. One example of the sequence number is a counter. It demands that the state information of the claimant be maintained after a protocol run. However, the bit length of the sequence number can be very short.


### 5.2. Efficiency Comparison

In this section, we compare the implementation costs of the improved protocol and the original one. Clearly, both protocols have the same secret storage cost due to the sameKLINK. As far as the computation cost is concerned, both protocols need one cryptographic hash computation to obtain {SRES, ACO} in each device. For the communication cost, the improved protocol has to transmit AU_RANDV, AU_RANDC, and SRES, whereas the original protocol only transmits AU_RAND and SRES. When AU_RANDV and AU_RANDC both are 128 bits, the improved protocol incurs an additional overhead of transmitting 128 bits in an authentication session. However, such overhead is insignificant in most of the devices. When AU_RANDV and AU_RANDC both are 64 bits, the communication cost of both protocols is the same. In conclusion, the improved protocol is as efficient as the original protocol.


## 5.1. Protocol Description

As shown in Figure5, we propose an improved protocol to repair the traceability weakness in the original protocol. The authentication session is now as follows.Step 1: the verifier generates a random number AU_RANDV as the challenge and then sends it to the claimant.Step 2: the claimant creates another random number AU_RANDC and calculates the authentication token {SRES, ACO} = E1 (KLINK, BD_ADDR, AU_RANDV, AU_RANDC). Herein, based on the SAFER + block cipher, it is necessary for the cryptographic hash algorithm E1 to have an input with a larger size. Alternatively, both AU_RANDV and AU_RANDC can be set to 64 bits, and the algorithm E1 remains the same.Step 3: the claimant sends the response AU_RANDC and SRES to the verifier.Step 4: upon receiving AU_RANDC and SRES, the verifier first uses AU_RANDC to calculate the authentication token {SRES, ACO} = E1 (KLINK, BD_ADDR, AU_RANDV, AU_RANDC). Then, it compares the received SRES with the counterpart calculated locally. If they are the same, the protocol run is successful and the verifier accepts the identity of the claimant; otherwise, the protocol run fails.Figure 5
Improved Bluetooth unilateral authentication protocol.Remark 1.
In practice, we can employ a non-symmetric split strategy for the random numbers AU_RANDV and AU_RANDC. If the risk of the tracking devices is low in some applications, the claimant’s AU_RANDC can be shortened to 32 bits or about, while keeping the length of the verifier’s AU_RANDV longer to ensure that the actual authentication strength is not degraded.The random number AU_RANDC can also be replaced with a sequence number, which never repeats in each protocol run. One example of the sequence number is a counter. It demands that the state information of the claimant be maintained after a protocol run. However, the bit length of the sequence number can be very short.


## 5.2. Efficiency Comparison

In this section, we compare the implementation costs of the improved protocol and the original one. Clearly, both protocols have the same secret storage cost due to the sameKLINK. As far as the computation cost is concerned, both protocols need one cryptographic hash computation to obtain {SRES, ACO} in each device. For the communication cost, the improved protocol has to transmit AU_RANDV, AU_RANDC, and SRES, whereas the original protocol only transmits AU_RAND and SRES. When AU_RANDV and AU_RANDC both are 128 bits, the improved protocol incurs an additional overhead of transmitting 128 bits in an authentication session. However, such overhead is insignificant in most of the devices. When AU_RANDV and AU_RANDC both are 64 bits, the communication cost of both protocols is the same. In conclusion, the improved protocol is as efficient as the original protocol.


## 6. Privacy Evaluation of Improved Unilateral Bluetooth Authentication Protocol

A fact we shall see from the proposed privacy weakness inSection 3 is that the design of the unilateral authentication protocol is extremely error-prone, even though it originated in standard documents. Therefore, to avoid the design defects as much as possible, we adopt the formal method to examine the privacy of the improved unilateral authentication protocol in the following.Let0,1∗ denote the set of finite binary strings and {0, 1}l represent the set of binary strings of the bit length l. Let Pr[Ev] be the probability of the event Ev and Pr[Ev1|Ev2] the conditional probability of the event Ev1 with respect to the event Ev2.


### 6.1. Model Definition

We use a formal model to evaluate the privacy of the unilateral authentication protocols. Similar work to improve the privacy analysis of the authentication protocols begins with the paper of Juels and Weis [37]. Under the Bluetooth network setting, let I = {1, 2, …, n} be a set of Bluetooth-enabled devices with either a claimant or a verifier. The unilateral authentication protocol Π rules how the claimant and the verifier behave during the protocol run. For any i, j ∈ I, let Πi,j be i’s instance of Π interacting with j. According to Π, Πi,j generates, transmits, and receives the message(s) to authenticate the claimant. To some extent, Πi,j can be treated as an efficiently computable function. The internal state of Πi,j includes the following variables:sid: the unique identifier of a protocol run.KLINK: the link key shared by both i and j.BD_ADDR: the claimant address.tran: a transcript ofi’s current protocol run so far, i.e., the ordered set of messages transmitted and received by i so far.δ: a Boolean variable set to true or false denoting whether to accept or reject at the end of the protocol run. This variable is merely valid in the verifier’s instance.Without loss of generality, we assume thati is the verifier and j is the intended claimant in the following. A protocol run can be modeled by collaboratively running Πi,j and Πj,i. At the end of the protocol run, i should either accept or reject the purported identity of j, which is indicated by Πi,j’s δ. Here, i verifies j by using Πi,j’s KLINK and BD_ADDR.A functionε: N⟶R is negligible in n if for all constants c ≥ 0 there always exists an integer N such that for all integers n > N it holds that ε (n) < n−c. If ε is negligible, then 1 − ε is said to be an overwhelming. Let k or 1k be the security parameter of the unilateral authentication protocol Π. We firstly define the notion of correctness as follows.Definition 1.
(correctness). A unilateral authentication protocol Π with the security parameterk is correct if, given any honest verifier i ∈ I and any honest claimant j ∈ I, the protocol run of the pair Πi,j and Πj,i succeeds with overwhelming probability in k.
Correctness of Π means that if both Πi,j and Πj,i collaboratively generate tran using the same KLINK and BD_ADDR, Πi,j’s δ is true at the end of the protocol run. Clearly, each Π must satisfy it. It is easy to check that both original and improved protocols are correct.


#### 6.1.1. Attacker

Assume that the attackerA has complete control over all communications during the run of Π. The capability of A is essentially done by specifying the actions that he is allowed to perform, i.e., a group of the oracles he can query. Under the Bluetooth network setting, the interaction between the devices and A is modeled by sending the queries to the oracles and receiving the results from the oracles. The oracles define how A interacts with Π.Launch (i, j) ⟶ {sid, Πi,j, Πj,i}: the Launch oracle means that the system initiates a unilateral authentication protocol run, where sid is set to a unique identifier for this run. Πi,j and Πj,i maintain the same KLINK and BD_ADDR. trans in both Πi,j and Πj,i are set to null, and δ in Πi,j is set to false.Send (m, sid, Πi,j) ⟶ m′ (resp. Send (m, sid, Πj,i) ⟶ m′): the Send oracle sends a message m to i (resp., j) and receives the answer m′, which should be sent to the counterpart j (resp., i). If m is valid according to Πi,j (resp., Πj,i), m is added to Πi,j’s (resp., Πj,i’s) tran simultaneously. Herein, m, m′∈1,0∗∪null, where null indicates that no message is transmitted.Execute (i, j) ⟶ {Πi,j, Πj,i, tran, sid}: the Execute oracle is used to group one Launch query and successive use of the Send queries to execute a complete protocol run between i’s Πi,j and j’s Πj,i. tran contains the transcript of all transmitted messages during this protocol run. Besides, the protocol run is identified by sid.Result (Πi,j) ⟶ x: the Result oracle can decide whether Πi,j successfully completes. That is, if Πi,j’s δ is true, then x = 1; otherwise, x = 0.Corrupt (Πi,j) ⟶ {KLINK} (resp., Corrupt (Πj,i) ⟶ {KLINK}): the Corrupt oracle returns the link key KLINK secretly stored in Πi,j (resp., Πj,i).In the following, we present an experiment to define the protocol privacy by using the above oracles.


#### 6.1.2. Privacy

As shown in Figure6 we present the experiment Pri − ExpΠ,A (k) to examine the privacy of the unilateral authentication protocol Π. In the setup stage, a set of devices are initiated by obtaining their KLINK and BD_ADDR. In the training I stage, the attacker A can select any pair of the devices and learn the run of Π by invoking the Launch, Send, Execute, Result, and Corrupt oracles. A then chooses two uncorrupted devices j0 and j1 at his will and provides them to the Test oracle in the challenge stage. The Test oracle flips a coin bit b∈ {0, 1} and returns a device jb back to A. Then, to guess the b, A can control the protocol runs between the claimant jb and any verifier i. That is, the training II stage continuously allows A to access the Launch, Send, Execute, and Result oracles. Finally, A should output his guessing of b. By this experiment, we propose the following definition for the protocol privacy.Figure 6
Privacy experiment for Bluetooth unilateral authentication protocol.Definition 2.
(privacy). A unilateral authentication protocol Π is private if, for any probabilistic polynomial-time (PPT) attackerA, the guessing advantage,(1)Pri−Adv∏,A=PrPri−Exp∏,Ak=1−PrPri−Exp∏,Ak=0,is negligible in the security parameter k.
We use Definition2 to examine the privacy of the unilateral authentication protocol as shown in Figure 2. The attacker A can invoke the Execute oracle to record a tran = {AU_RAND, SRES} between a claimant j and a verifier i during the training I stage. Then, A submits j0 = j and any other j1∈I and calls the oracle Test (j0, j1) in the challenge stage. During the training II stage, A calls the oracle Launch (i, jb) to obtain Πjb,i and sid and then invokes the oracle Send (AU_RAND, sid, Πjb,i) to receive the corresponding SRES. A outputs the guess bit b′ = 0 if the received SRES is equal to the recorded SRES during the training I stage. Otherwise, he outputs the guess bit b′ = 1. Let ν be the probability that both the Send (AU_RAND, sid, Πj0,i) and the Send (AU_RAND, sid, Πj1,i) output the same SRES. We have(2)Pri−Adv∏,A=PrPri−Exp∏,Ak=1−PrPri−Exp∏,Ak=0=PrPri−Exp∏,Ak=1|b=0Prb=0+PrPri−Exp∏,Ak=1|b=1Prb=1−PrPriExp∏,Ak=0|b=0Prb=0−PrPri−Exp∏,Ak=0|b=1Prb=1|≤1−ν2+12−ν2−0=1−ν.
Obviously,ν is negligible in the security parameter k. The protocol as shown in Figure 2 does not satisfy Definition 2 and therefore is not private. Consider the improved unilateral authentication protocol as shown in Figure 5. Although the attacker A can intercept the previous values AU_RANDV, AU_RANDC, and SRES exchanged between Device 1 and Device 2, he cannot reuse them to identify the target Device 1. In the subsequent protocol run, A can replay the previous AU_RANDV to Device 1. However, Device 1 should compute a different SRES because a different AU_RANDC is generated as an input of the algorithm E1. As a result, A cannot determine the identity of Device 1 by comparing the received SRES with the one recorded in the past protocol run. Certainly, the above privacy discussion is informal. In the following, we will present the privacy result of the improved protocol under our formal model.


### 6.2. Privacy Property and Its Proof

To evaluate the privacy of the improved unilateral authentication protocol, we need to use the keyed pseudorandom function assumption [38]. A keyed function F receives for input some K∈ {0, 1}k and m∈0,1∗ and outputs some h∈0,1∗. Here, K is the key chosen uniformly at random. F is a keyed pseudorandom function such that no polynomial-time distinguisher D can detect if it is given a string sampled according to F or a real random function f. The formal definition is given as follows.Definition 3.
LetF: {0, 1}k × {0, I}ll ⟶ {0, 1}l2 be an efficient keyed function. We say F is a keyed pseudorandom function if, for all PPT distinguishers D, there exists a negligible function ε such that(3)PrD1k,FK=1−PrD1k,f=1≤εk,where the k-bit key K is chosen uniformly at random and f is chosen uniformly at random from the set of random functions mapping l1-bit strings to l2-bit strings.
Note thatD in Definition 3 has oracle access to the function in question (either F or f). That is to say, D is allowed to query the oracle at any time x, in response to which the oracle returns the value of the function evaluated at x. Finally, D outputs 1 if it makes a correct guess. Now, we have the following theorem.Theorem 1.
Let Π be the improved unilateral authentication protocol as shown in Figure5. If the algorithm E1 in Π is a keyed pseudorandom function and the k-bit link key KLINK is kept secret, then Π is private in k under Definition 2.Proof.
We know that the Corrupt oracle cannot help the attackerA to guess the random bit b in the experiment Pri − ExpΠ,A (k). The reason is that all KLINKs of the pairing devices are independent and the oracle Corrupt is not allowed if the corresponding KLINK is used in the training II stage. Hence, we do not consider the Corrupt oracle in the following discussions.
During the training II stage in the experiment Pri − ExpΠ,A (k), the attacker A can interact with the claimant jb. We specify a simulator Sim to simulate jb’s behavior in each run of Π in this stage. However, Sim has no knowledge of the value of the random bit b or the link key KLINK in Π. We demonstrate that A’s interaction with Sim will be computationally indistinguishable from a real interaction with jb. This means that A cannot identify jb at the guess stage because A gains no knowledge from its interaction with jb by the runs of Π.
Recall that the attackerA selects j0 and j1 in the challenge stage of the experiment Pri − ExpΠ,A (k). Let L be the full list of the session transcript tran related to both j0 and j1 in the training I stage. Let L′ be the full list of the session transcript tran of jb in the training II stage. When A invokes the Launch, Send, Execute, and Result oracles during the training II stage, Sim simulates the four oracles as follows.Launch oracle: when the attackerA calls Launch (i, jb), Sim generates its sid, Π (1k, i, jb, null), and Π (1k, jb, i, null) and then sends them to A. Here, Π (1k, i, jb, null) and Π (1k, jb, i, null) are, respectively, used to simulate Πi,jb and Πjb,i and null means that Sim does not know the link key KLINK.Send oracle: (1) When the attackerA calls Send (null, sid, Π (1k, i, jb, null)), Sim randomly generates the AU_RANDV as the verifier i in Π, records the AU_RANDV in its L′, and sends it to A. (2) When A calls Send (AU_RANDV, sid, Π (1k, jb, i, null)) and AU_RANDV is generated by Sim, Sim generates the random AU_RANDC and the random SRES itself and records them in its L′ and then sends the AU_RANDC and SRES to A. Sim terminates the protocol run if A calls Send (AU_RANDV, sid, Π (1k, jb, i, null)) and Sim does not generate AU_RANDV. (3) When A calls Send ({AU_RANDC, SRES}, sid, Π (1k, i, jb, null, AU_RANDV)), Sim sends the “accept” decision to A if {AU_RANDV, AU_RANDC, SRES} has existed in its L′; otherwise, Sim sends the “reject” decision to A.Execute oracle: to simulate Execute (i, jb), Sim generates sid, AU_RANDV, AU_RANDC, and SRES just like the Launch oracle and the Send oracle; records {AU_RANDV, AU_RANDC, SRES} in its L′; and then sends them to A.Result oracle: when the attackerA invokes Result (Π (1k, i, jb, null, tran)), Sim returns 1 to A if the tran is in its L′; otherwise, it returns 0 to A. In the case of calling Result (Π (1k, i, jb, KLINK, tran)), Sim should replay the query to i or jb and return the corresponding response to A.
To distinguish Sim’s training II stage from a real training II stage, the attackerA must be able to identify at least one invalid session between the claimant jb and any other verifier i. In other words, A must rule out at least one tran = {AU_RANDV, AU_RANDC, SRES} in order to determine that Sim is present during the training II stage. Assume that A, respectively, makes at most q (k) queries to the Send oracle and the Execute oracle in each training stage of the experiment Pri − ExpΠ,A (k), where q (k) is a polynomial function. Consequently, one of the following two cases must occur at some point during the experiment Pri − ExpΠ,A (k).Case 1: there are two session transcripts:AU_RANDVL,AU_RANDCL,SRESL∈L and AU_RANDVL′,AU_RANDCL′,SRESL′∈L′ such that AU_RANDVL=AU_RANDVL′ and AU_RANDCL=AU_RANDCL′. We know that SRESL′ is randomly generated by Sim. Hence, the attacker A can figure out Sim by verifying whether SRESL is equal to SRESL′. Let |L| and |L′| denote, respectively, the number of the session transcripts in L and L′. We have |L| ≤ q (k) and |L′| ≤ q (k) because A makes, respectively, at most q (k) Send and Execute calls in each corresponding training stage. A can control the AU_RANDVL and AU_RANDVL′; however, AU_RANDCL and AU_RANDCL′ are, respectively, generated by the claimant jb and Sim. Since the values AU_RANDCL and AU_RANDCL′ are all random k-bit values, Case 1 occurs with the probability at most q (k)2/2k.Case 2: Sim randomly chooses SRES in the session. Comparatively, thejb should use the algorithm E1 to calculate SRES. Hence, the attacker A depends on whether SERS is randomly chosen or calculated to recognize Sim. We know that the algorithm E1 is a keyed pseudorandom function (see Definition 3). According to (3), the probability u that A can pick out Sim is(4)uk≤PrD1k,FK=1−PrD1k,f=1≤εk.
Hence, the polynomially bounded attackerA can distinguish Sim from the real jb with the negligible probability at most q (k)2/2k + u (k) ≤ q (k)2/2k + ε (k).
Due to Theorem1, the improved unilateral authentication protocol can prevent the attacker from identifying, tracing, or linking to the device, if and only if the device does not compromise its secret parameter KLINK stored in the memory.


## 6.1. Model Definition

We use a formal model to evaluate the privacy of the unilateral authentication protocols. Similar work to improve the privacy analysis of the authentication protocols begins with the paper of Juels and Weis [37]. Under the Bluetooth network setting, let I = {1, 2, …, n} be a set of Bluetooth-enabled devices with either a claimant or a verifier. The unilateral authentication protocol Π rules how the claimant and the verifier behave during the protocol run. For any i, j ∈ I, let Πi,j be i’s instance of Π interacting with j. According to Π, Πi,j generates, transmits, and receives the message(s) to authenticate the claimant. To some extent, Πi,j can be treated as an efficiently computable function. The internal state of Πi,j includes the following variables:sid: the unique identifier of a protocol run.KLINK: the link key shared by both i and j.BD_ADDR: the claimant address.tran: a transcript ofi’s current protocol run so far, i.e., the ordered set of messages transmitted and received by i so far.δ: a Boolean variable set to true or false denoting whether to accept or reject at the end of the protocol run. This variable is merely valid in the verifier’s instance.Without loss of generality, we assume thati is the verifier and j is the intended claimant in the following. A protocol run can be modeled by collaboratively running Πi,j and Πj,i. At the end of the protocol run, i should either accept or reject the purported identity of j, which is indicated by Πi,j’s δ. Here, i verifies j by using Πi,j’s KLINK and BD_ADDR.A functionε: N⟶R is negligible in n if for all constants c ≥ 0 there always exists an integer N such that for all integers n > N it holds that ε (n) < n−c. If ε is negligible, then 1 − ε is said to be an overwhelming. Let k or 1k be the security parameter of the unilateral authentication protocol Π. We firstly define the notion of correctness as follows.Definition 1.
(correctness). A unilateral authentication protocol Π with the security parameterk is correct if, given any honest verifier i ∈ I and any honest claimant j ∈ I, the protocol run of the pair Πi,j and Πj,i succeeds with overwhelming probability in k.
Correctness of Π means that if both Πi,j and Πj,i collaboratively generate tran using the same KLINK and BD_ADDR, Πi,j’s δ is true at the end of the protocol run. Clearly, each Π must satisfy it. It is easy to check that both original and improved protocols are correct.


### 6.1.1. Attacker

Assume that the attackerA has complete control over all communications during the run of Π. The capability of A is essentially done by specifying the actions that he is allowed to perform, i.e., a group of the oracles he can query. Under the Bluetooth network setting, the interaction between the devices and A is modeled by sending the queries to the oracles and receiving the results from the oracles. The oracles define how A interacts with Π.Launch (i, j) ⟶ {sid, Πi,j, Πj,i}: the Launch oracle means that the system initiates a unilateral authentication protocol run, where sid is set to a unique identifier for this run. Πi,j and Πj,i maintain the same KLINK and BD_ADDR. trans in both Πi,j and Πj,i are set to null, and δ in Πi,j is set to false.Send (m, sid, Πi,j) ⟶ m′ (resp. Send (m, sid, Πj,i) ⟶ m′): the Send oracle sends a message m to i (resp., j) and receives the answer m′, which should be sent to the counterpart j (resp., i). If m is valid according to Πi,j (resp., Πj,i), m is added to Πi,j’s (resp., Πj,i’s) tran simultaneously. Herein, m, m′∈1,0∗∪null, where null indicates that no message is transmitted.Execute (i, j) ⟶ {Πi,j, Πj,i, tran, sid}: the Execute oracle is used to group one Launch query and successive use of the Send queries to execute a complete protocol run between i’s Πi,j and j’s Πj,i. tran contains the transcript of all transmitted messages during this protocol run. Besides, the protocol run is identified by sid.Result (Πi,j) ⟶ x: the Result oracle can decide whether Πi,j successfully completes. That is, if Πi,j’s δ is true, then x = 1; otherwise, x = 0.Corrupt (Πi,j) ⟶ {KLINK} (resp., Corrupt (Πj,i) ⟶ {KLINK}): the Corrupt oracle returns the link key KLINK secretly stored in Πi,j (resp., Πj,i).In the following, we present an experiment to define the protocol privacy by using the above oracles.


### 6.1.2. Privacy

As shown in Figure6 we present the experiment Pri − ExpΠ,A (k) to examine the privacy of the unilateral authentication protocol Π. In the setup stage, a set of devices are initiated by obtaining their KLINK and BD_ADDR. In the training I stage, the attacker A can select any pair of the devices and learn the run of Π by invoking the Launch, Send, Execute, Result, and Corrupt oracles. A then chooses two uncorrupted devices j0 and j1 at his will and provides them to the Test oracle in the challenge stage. The Test oracle flips a coin bit b∈ {0, 1} and returns a device jb back to A. Then, to guess the b, A can control the protocol runs between the claimant jb and any verifier i. That is, the training II stage continuously allows A to access the Launch, Send, Execute, and Result oracles. Finally, A should output his guessing of b. By this experiment, we propose the following definition for the protocol privacy.Figure 6
Privacy experiment for Bluetooth unilateral authentication protocol.Definition 2.
(privacy). A unilateral authentication protocol Π is private if, for any probabilistic polynomial-time (PPT) attackerA, the guessing advantage,(1)Pri−Adv∏,A=PrPri−Exp∏,Ak=1−PrPri−Exp∏,Ak=0,is negligible in the security parameter k.
We use Definition2 to examine the privacy of the unilateral authentication protocol as shown in Figure 2. The attacker A can invoke the Execute oracle to record a tran = {AU_RAND, SRES} between a claimant j and a verifier i during the training I stage. Then, A submits j0 = j and any other j1∈I and calls the oracle Test (j0, j1) in the challenge stage. During the training II stage, A calls the oracle Launch (i, jb) to obtain Πjb,i and sid and then invokes the oracle Send (AU_RAND, sid, Πjb,i) to receive the corresponding SRES. A outputs the guess bit b′ = 0 if the received SRES is equal to the recorded SRES during the training I stage. Otherwise, he outputs the guess bit b′ = 1. Let ν be the probability that both the Send (AU_RAND, sid, Πj0,i) and the Send (AU_RAND, sid, Πj1,i) output the same SRES. We have(2)Pri−Adv∏,A=PrPri−Exp∏,Ak=1−PrPri−Exp∏,Ak=0=PrPri−Exp∏,Ak=1|b=0Prb=0+PrPri−Exp∏,Ak=1|b=1Prb=1−PrPriExp∏,Ak=0|b=0Prb=0−PrPri−Exp∏,Ak=0|b=1Prb=1|≤1−ν2+12−ν2−0=1−ν.
Obviously,ν is negligible in the security parameter k. The protocol as shown in Figure 2 does not satisfy Definition 2 and therefore is not private. Consider the improved unilateral authentication protocol as shown in Figure 5. Although the attacker A can intercept the previous values AU_RANDV, AU_RANDC, and SRES exchanged between Device 1 and Device 2, he cannot reuse them to identify the target Device 1. In the subsequent protocol run, A can replay the previous AU_RANDV to Device 1. However, Device 1 should compute a different SRES because a different AU_RANDC is generated as an input of the algorithm E1. As a result, A cannot determine the identity of Device 1 by comparing the received SRES with the one recorded in the past protocol run. Certainly, the above privacy discussion is informal. In the following, we will present the privacy result of the improved protocol under our formal model.


## 6.1.1. Attacker

Assume that the attackerA has complete control over all communications during the run of Π. The capability of A is essentially done by specifying the actions that he is allowed to perform, i.e., a group of the oracles he can query. Under the Bluetooth network setting, the interaction between the devices and A is modeled by sending the queries to the oracles and receiving the results from the oracles. The oracles define how A interacts with Π.Launch (i, j) ⟶ {sid, Πi,j, Πj,i}: the Launch oracle means that the system initiates a unilateral authentication protocol run, where sid is set to a unique identifier for this run. Πi,j and Πj,i maintain the same KLINK and BD_ADDR. trans in both Πi,j and Πj,i are set to null, and δ in Πi,j is set to false.Send (m, sid, Πi,j) ⟶ m′ (resp. Send (m, sid, Πj,i) ⟶ m′): the Send oracle sends a message m to i (resp., j) and receives the answer m′, which should be sent to the counterpart j (resp., i). If m is valid according to Πi,j (resp., Πj,i), m is added to Πi,j’s (resp., Πj,i’s) tran simultaneously. Herein, m, m′∈1,0∗∪null, where null indicates that no message is transmitted.Execute (i, j) ⟶ {Πi,j, Πj,i, tran, sid}: the Execute oracle is used to group one Launch query and successive use of the Send queries to execute a complete protocol run between i’s Πi,j and j’s Πj,i. tran contains the transcript of all transmitted messages during this protocol run. Besides, the protocol run is identified by sid.Result (Πi,j) ⟶ x: the Result oracle can decide whether Πi,j successfully completes. That is, if Πi,j’s δ is true, then x = 1; otherwise, x = 0.Corrupt (Πi,j) ⟶ {KLINK} (resp., Corrupt (Πj,i) ⟶ {KLINK}): the Corrupt oracle returns the link key KLINK secretly stored in Πi,j (resp., Πj,i).In the following, we present an experiment to define the protocol privacy by using the above oracles.


## 6.1.2. Privacy

As shown in Figure6 we present the experiment Pri − ExpΠ,A (k) to examine the privacy of the unilateral authentication protocol Π. In the setup stage, a set of devices are initiated by obtaining their KLINK and BD_ADDR. In the training I stage, the attacker A can select any pair of the devices and learn the run of Π by invoking the Launch, Send, Execute, Result, and Corrupt oracles. A then chooses two uncorrupted devices j0 and j1 at his will and provides them to the Test oracle in the challenge stage. The Test oracle flips a coin bit b∈ {0, 1} and returns a device jb back to A. Then, to guess the b, A can control the protocol runs between the claimant jb and any verifier i. That is, the training II stage continuously allows A to access the Launch, Send, Execute, and Result oracles. Finally, A should output his guessing of b. By this experiment, we propose the following definition for the protocol privacy.Figure 6
Privacy experiment for Bluetooth unilateral authentication protocol.Definition 2.
(privacy). A unilateral authentication protocol Π is private if, for any probabilistic polynomial-time (PPT) attackerA, the guessing advantage,(1)Pri−Adv∏,A=PrPri−Exp∏,Ak=1−PrPri−Exp∏,Ak=0,is negligible in the security parameter k.
We use Definition2 to examine the privacy of the unilateral authentication protocol as shown in Figure 2. The attacker A can invoke the Execute oracle to record a tran = {AU_RAND, SRES} between a claimant j and a verifier i during the training I stage. Then, A submits j0 = j and any other j1∈I and calls the oracle Test (j0, j1) in the challenge stage. During the training II stage, A calls the oracle Launch (i, jb) to obtain Πjb,i and sid and then invokes the oracle Send (AU_RAND, sid, Πjb,i) to receive the corresponding SRES. A outputs the guess bit b′ = 0 if the received SRES is equal to the recorded SRES during the training I stage. Otherwise, he outputs the guess bit b′ = 1. Let ν be the probability that both the Send (AU_RAND, sid, Πj0,i) and the Send (AU_RAND, sid, Πj1,i) output the same SRES. We have(2)Pri−Adv∏,A=PrPri−Exp∏,Ak=1−PrPri−Exp∏,Ak=0=PrPri−Exp∏,Ak=1|b=0Prb=0+PrPri−Exp∏,Ak=1|b=1Prb=1−PrPriExp∏,Ak=0|b=0Prb=0−PrPri−Exp∏,Ak=0|b=1Prb=1|≤1−ν2+12−ν2−0=1−ν.
Obviously,ν is negligible in the security parameter k. The protocol as shown in Figure 2 does not satisfy Definition 2 and therefore is not private. Consider the improved unilateral authentication protocol as shown in Figure 5. Although the attacker A can intercept the previous values AU_RANDV, AU_RANDC, and SRES exchanged between Device 1 and Device 2, he cannot reuse them to identify the target Device 1. In the subsequent protocol run, A can replay the previous AU_RANDV to Device 1. However, Device 1 should compute a different SRES because a different AU_RANDC is generated as an input of the algorithm E1. As a result, A cannot determine the identity of Device 1 by comparing the received SRES with the one recorded in the past protocol run. Certainly, the above privacy discussion is informal. In the following, we will present the privacy result of the improved protocol under our formal model.


## 6.2. Privacy Property and Its Proof

To evaluate the privacy of the improved unilateral authentication protocol, we need to use the keyed pseudorandom function assumption [38]. A keyed function F receives for input some K∈ {0, 1}k and m∈0,1∗ and outputs some h∈0,1∗. Here, K is the key chosen uniformly at random. F is a keyed pseudorandom function such that no polynomial-time distinguisher D can detect if it is given a string sampled according to F or a real random function f. The formal definition is given as follows.Definition 3.
LetF: {0, 1}k × {0, I}ll ⟶ {0, 1}l2 be an efficient keyed function. We say F is a keyed pseudorandom function if, for all PPT distinguishers D, there exists a negligible function ε such that(3)PrD1k,FK=1−PrD1k,f=1≤εk,where the k-bit key K is chosen uniformly at random and f is chosen uniformly at random from the set of random functions mapping l1-bit strings to l2-bit strings.
Note thatD in Definition 3 has oracle access to the function in question (either F or f). That is to say, D is allowed to query the oracle at any time x, in response to which the oracle returns the value of the function evaluated at x. Finally, D outputs 1 if it makes a correct guess. Now, we have the following theorem.Theorem 1.
Let Π be the improved unilateral authentication protocol as shown in Figure5. If the algorithm E1 in Π is a keyed pseudorandom function and the k-bit link key KLINK is kept secret, then Π is private in k under Definition 2.Proof.
We know that the Corrupt oracle cannot help the attackerA to guess the random bit b in the experiment Pri − ExpΠ,A (k). The reason is that all KLINKs of the pairing devices are independent and the oracle Corrupt is not allowed if the corresponding KLINK is used in the training II stage. Hence, we do not consider the Corrupt oracle in the following discussions.
During the training II stage in the experiment Pri − ExpΠ,A (k), the attacker A can interact with the claimant jb. We specify a simulator Sim to simulate jb’s behavior in each run of Π in this stage. However, Sim has no knowledge of the value of the random bit b or the link key KLINK in Π. We demonstrate that A’s interaction with Sim will be computationally indistinguishable from a real interaction with jb. This means that A cannot identify jb at the guess stage because A gains no knowledge from its interaction with jb by the runs of Π.
Recall that the attackerA selects j0 and j1 in the challenge stage of the experiment Pri − ExpΠ,A (k). Let L be the full list of the session transcript tran related to both j0 and j1 in the training I stage. Let L′ be the full list of the session transcript tran of jb in the training II stage. When A invokes the Launch, Send, Execute, and Result oracles during the training II stage, Sim simulates the four oracles as follows.Launch oracle: when the attackerA calls Launch (i, jb), Sim generates its sid, Π (1k, i, jb, null), and Π (1k, jb, i, null) and then sends them to A. Here, Π (1k, i, jb, null) and Π (1k, jb, i, null) are, respectively, used to simulate Πi,jb and Πjb,i and null means that Sim does not know the link key KLINK.Send oracle: (1) When the attackerA calls Send (null, sid, Π (1k, i, jb, null)), Sim randomly generates the AU_RANDV as the verifier i in Π, records the AU_RANDV in its L′, and sends it to A. (2) When A calls Send (AU_RANDV, sid, Π (1k, jb, i, null)) and AU_RANDV is generated by Sim, Sim generates the random AU_RANDC and the random SRES itself and records them in its L′ and then sends the AU_RANDC and SRES to A. Sim terminates the protocol run if A calls Send (AU_RANDV, sid, Π (1k, jb, i, null)) and Sim does not generate AU_RANDV. (3) When A calls Send ({AU_RANDC, SRES}, sid, Π (1k, i, jb, null, AU_RANDV)), Sim sends the “accept” decision to A if {AU_RANDV, AU_RANDC, SRES} has existed in its L′; otherwise, Sim sends the “reject” decision to A.Execute oracle: to simulate Execute (i, jb), Sim generates sid, AU_RANDV, AU_RANDC, and SRES just like the Launch oracle and the Send oracle; records {AU_RANDV, AU_RANDC, SRES} in its L′; and then sends them to A.Result oracle: when the attackerA invokes Result (Π (1k, i, jb, null, tran)), Sim returns 1 to A if the tran is in its L′; otherwise, it returns 0 to A. In the case of calling Result (Π (1k, i, jb, KLINK, tran)), Sim should replay the query to i or jb and return the corresponding response to A.
To distinguish Sim’s training II stage from a real training II stage, the attackerA must be able to identify at least one invalid session between the claimant jb and any other verifier i. In other words, A must rule out at least one tran = {AU_RANDV, AU_RANDC, SRES} in order to determine that Sim is present during the training II stage. Assume that A, respectively, makes at most q (k) queries to the Send oracle and the Execute oracle in each training stage of the experiment Pri − ExpΠ,A (k), where q (k) is a polynomial function. Consequently, one of the following two cases must occur at some point during the experiment Pri − ExpΠ,A (k).Case 1: there are two session transcripts:AU_RANDVL,AU_RANDCL,SRESL∈L and AU_RANDVL′,AU_RANDCL′,SRESL′∈L′ such that AU_RANDVL=AU_RANDVL′ and AU_RANDCL=AU_RANDCL′. We know that SRESL′ is randomly generated by Sim. Hence, the attacker A can figure out Sim by verifying whether SRESL is equal to SRESL′. Let |L| and |L′| denote, respectively, the number of the session transcripts in L and L′. We have |L| ≤ q (k) and |L′| ≤ q (k) because A makes, respectively, at most q (k) Send and Execute calls in each corresponding training stage. A can control the AU_RANDVL and AU_RANDVL′; however, AU_RANDCL and AU_RANDCL′ are, respectively, generated by the claimant jb and Sim. Since the values AU_RANDCL and AU_RANDCL′ are all random k-bit values, Case 1 occurs with the probability at most q (k)2/2k.Case 2: Sim randomly chooses SRES in the session. Comparatively, thejb should use the algorithm E1 to calculate SRES. Hence, the attacker A depends on whether SERS is randomly chosen or calculated to recognize Sim. We know that the algorithm E1 is a keyed pseudorandom function (see Definition 3). According to (3), the probability u that A can pick out Sim is(4)uk≤PrD1k,FK=1−PrD1k,f=1≤εk.
Hence, the polynomially bounded attackerA can distinguish Sim from the real jb with the negligible probability at most q (k)2/2k + u (k) ≤ q (k)2/2k + ε (k).
Due to Theorem1, the improved unilateral authentication protocol can prevent the attacker from identifying, tracing, or linking to the device, if and only if the device does not compromise its secret parameter KLINK stored in the memory.


## 7. Other Countermeasures against Proposed Weakness

### 7.1. Limiting Authentication Failure Attempts

Clearly, the proposed privacy weakness can be partly repaired if the claimant limits the number of failed authentication attempts for each link key. We know the claimant can confirm the authentication failure because the verifier should terminate its subsequent communication with the claimant. Hence, a countermeasure is to change its link key whenever FA >t, where FA is the number of failed authentication attempts since the link key was last changed and t is the threshold number of failed attempts. If t = 0, then the attacker can at most track the identity of the claimant one time. However, if the value of t is too small, it may lead to the high overheads of the pairing devices. The reason is that the device’s hardware and software faults may also cause authentication failure attempts. In this situation, the pairing devices need frequently to update their link key by running the pairing and link key generation procedure.


### 7.2. Avoiding Unilateral Authentication Protocol

To overcome the proposed privacy weakness, it is required that both pairing devices always execute the mutual authentication protocol instead of the unilateral authentication protocol. However, this countermeasure has disadvantages as follows.The mutual authentication protocol is performed, only if both paring devices support the mutual authentication protocol. Otherwise, the unilateral authentication protocol is performed. In addition, during the link initialization stage, the attacker can also cheat the paring devices to be backward compatible with the unilateral authentication protocol. One way of deceiving is by intercepting and modifying the Bluetooth data packets of the device capabilities.The mutual authentication protocol is merely used when the link key has been generated using SSP with theP− 256 Elliptic Curve. Comparatively, the unilateral authentication protocol supports SSP with not only the P− 256 Elliptic Curve but also the P− 128 Elliptic Curve.The unilateral authentication suffices for many Bluetooth MCS cases. Further, it is more desirable in the Bluetooth MCS, since the mutual authentication incurs more implementation costs compared with the unilateral authentication.


## 7.1. Limiting Authentication Failure Attempts

Clearly, the proposed privacy weakness can be partly repaired if the claimant limits the number of failed authentication attempts for each link key. We know the claimant can confirm the authentication failure because the verifier should terminate its subsequent communication with the claimant. Hence, a countermeasure is to change its link key whenever FA >t, where FA is the number of failed authentication attempts since the link key was last changed and t is the threshold number of failed attempts. If t = 0, then the attacker can at most track the identity of the claimant one time. However, if the value of t is too small, it may lead to the high overheads of the pairing devices. The reason is that the device’s hardware and software faults may also cause authentication failure attempts. In this situation, the pairing devices need frequently to update their link key by running the pairing and link key generation procedure.


## 7.2. Avoiding Unilateral Authentication Protocol

To overcome the proposed privacy weakness, it is required that both pairing devices always execute the mutual authentication protocol instead of the unilateral authentication protocol. However, this countermeasure has disadvantages as follows.The mutual authentication protocol is performed, only if both paring devices support the mutual authentication protocol. Otherwise, the unilateral authentication protocol is performed. In addition, during the link initialization stage, the attacker can also cheat the paring devices to be backward compatible with the unilateral authentication protocol. One way of deceiving is by intercepting and modifying the Bluetooth data packets of the device capabilities.The mutual authentication protocol is merely used when the link key has been generated using SSP with theP− 256 Elliptic Curve. Comparatively, the unilateral authentication protocol supports SSP with not only the P− 256 Elliptic Curve but also the P− 128 Elliptic Curve.The unilateral authentication suffices for many Bluetooth MCS cases. Further, it is more desirable in the Bluetooth MCS, since the mutual authentication incurs more implementation costs compared with the unilateral authentication.


## 8. Conclusions

We investigate the traceability weakness relating to the unilateral authentication protocol in the Bluetooth standard, which is widely applied in the Bluetooth-enabled devices. The authentication service should provide strong privacy protection in fear of vulnerabilities and abuse mounting. Such privacy requirement for the weak authentication protocol is reinforced by the possibility of more and more Bluetooth-enabled device abuses in the real world, such as the Bluetooth MCS. An improved unilateral authentication protocol is thus proposed to overcome the weakness of traceability. Our improved protocol is simple and easy to implement in Bluetooth-enabled devices, though with a little extra overheads. In addition, non-protocol countermeasures are also suggested to fix the weakness of traceability. Certainly, the unilateral authentication protocol is still unable to assure the overall privacy of the Bluetooth-enabled devices and their networks. Nevertheless, we believe that our results are a steady step toward enhancing Bluetooth security solutions. Our future work is to study the privacy problems of the mutual authentication protocol and the confidentiality procedure in accordance with the Bluetooth standard.



---

*Source: 5598574-2021-06-08.xml*