# LAAP: Lightweight Anonymous Authentication Protocol for IoT Edge Devices Based on Elliptic Curve

Authors: Xinghui Zhu; Zhong Ren; Ji He; Baoquan Ren; Shuangrui Zhao; Pinchang Zhang
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

The massive heterogeneous devices and open channels of the Internet of Things (IoT) lead to low efficiency and privacy leakage in the authentication process, which brings great challenges to identity authentication. This paper focuses on the anonymous authentication between the IoT edge device and the cloud server. In this work, we first propose a novel lightweight anonymous authentication protocol (LAAP) to meet security and efficiency requirements. Especially, the proposed protocol uses dynamic pseudonyms to prevent the traceable attacks caused by fixed identity identification and also uses symmetric encryption to optimize the server’s search for anonymous device information, and the time complexity is reduced fromOn to O1. Then, the formal security analysis and informal security analysis are provided to prove the security of the proposed protocol. Finally, extensive numerical results indicate that the proposed LAAP protocol is superior to the benchmarks in terms of computing overhead and communication overhead, while the storage overhead is consistent with the lowest level among other protocols.


---

## Body

## 1. Introduction

The Internet of Things (IoT) aims to connect massive sensing devices through wireless networks to realize information interaction between the physical world and the virtual world. With the wide application of IoT, it has been involved in all walks of life, such as the Internet of Vehicles, Internet of Medical Things, and Smart City. According to GSMA forecast, the number of IoT devices worldwide will reach about23.3 billion in 2025 [1]. Due to the limited storage, computing, communication, and power capabilities of IoT sensing devices, combining edge-embedded devices with cloud computing creates a new paradigm called CloudIoT [2]. Under this paradigm, embedded devices can rely on the processing power of cloud computing and use various services provided by cloud computing. However, when an embedded device establishes a communication connection with a cloud server, security is the primary concern.In recent years, privacy and data security issues caused by IoT terminal devices have frequently occurred. On June 8, 2020, security experts disclosed a new UPnP vulnerability named “Call Stranger” [3], which affects the security of billions of devices, including the TV and network equipment of ASUS, Belkin, Dell, Samsung, TP-Link, and other companies. The vulnerability could be exploited by a remote, unauthenticated attacker. In September 2021, researchers discovered a high-level security vulnerability CVE-2021-36260 in Hikvision IP camera/NVR device firmware. The attack can fully control the device through the shell and obtain any information of the owner and further laterally attack the internal network without leaving any daily login information [4]. The report released by the Unit 42 team [5] shows that 98% of IoT devices leak user privacy due to unencrypted traffic, 57% of devices are vulnerable to moderate or severe attacks, and devices have become the preferred target for attackers.Authentication can guarantee the identity legitimacy of communication parties in the IoT and is a key technology to solve security problems. The authentication process usually involves two parts, i.e., identity authentication and key negotiation. Identity authentication is to ensure the legitimacy of the identities of both communication parties. Key negotiation is used to establish a session key for subsequent security access and secure data transmission. Note that security authentication protocols need to consider the following principles: (1) for lightweight, most IoT devices cannot support complex authentication protocols because of their limited computing resource [6]; (2) for privacy protection, during the interaction of the device, the advanced techniques (e.g., anonymity and blockchain) need to be adopted to prevent malicious attackers from obtaining the private information of the devices and users [7].


### 1.1. Related Work

To implement the security authentication of IoT devices, various protocols and methods were studied. Kalra and Sood in [8] proposed a two-way authentication scheme to realize mutual authentication and meet essential security requirements. Considering the security defects and structural problems of the protocol [8], the improved protocols in [9, 10] were proposed to defend against server emulation attacks. Rostampour et al. then proposed a privacy-preserving anonymous authentication protocol named ECCbAP in [11]; the results indicated that the proposed protocol can achieve the untraceable purpose by traversing the registry. Then, the authors in [12] proposed an authentication protocol based on bilinear pairing to solve the problems of privacy protection and authentication table theft. Subsequently, the enhanced IoT mutual authentication protocol and improved ECC-based authentication protocol were proposed in [13, 14], respectively. To defend against more types of attacks including known temporary information attacks, DoS attacks, Panda and Chattopadhyay proposed an anonymous authentication scheme integrating a password validator in [15]. Further, Bhuarya et al. in [16] proposed an enhanced authentication scheme to defend known session-specific temporary information attack, where the hypertext transfer protocol (HTTP) cookies were used to authenticate clients. However, the large exponential powers employed by these protocols leads to a large amount of computation.The dynamic pseudonym is an effective method to solve traceable problems. A pseudonym ID is used to conduct authentication between client and server and is dynamically updated after completion of authentication. Das et al. first proposed an authentication protocol [17] where dynamic ID technology was used to avoid the risk of ID theft. However, the protocol suffers from smart card theft attacks. Then, Jiang and Das et al. devoted to solving the problem in [18, 19], respectively. Notice when the above schemes are attacked asynchronously, i.e., the attacker blocks the exchange messages of the authentication protocol, and the interaction between the authentication parties is out of sync, such that the protocol cannot work. Thus, Gope et al. in [20–23] studied the authentication scheme based on emergency ID and secret key technology to solve the problem of asynchronous attack. In such schemes, clients and servers share a set of emergency IDs and keys in addition to dynamic pseudonyms. Once the dynamic pseudonyms are out of sync, emergency IDs and keys are used to interact. However, the emergency IDs and keys occupy a large amount of storage space, and once the emergency ID and emergency key are used up, the device must be reregistered. Recently, some researchers devoted to designing grant-free access scheme for M2M communications [24] and used the advanced methods to realize the authentication, e.g., deep learning [25, 26] and blockchain [27, 28]. However, they are not suitable for IoT devices with limited computing overhead.


### 1.2. Motivation and Contribution

To sum up, it can be found that the mentioned authentication protocols based on identity and pseudonym do not consider the privacy protection and cannot resist traceable attacks. For example, if the long-term key is leaked, the attacker can simulate the session key negotiation between the terminal and the server and occupy the position of the legitimate device. As a result, the legitimate device cannot carry out normal session key negotiation. Furthermore, during authentication process, the server needs to traverse the password verifier table to find the relevant registration information, and the search time increases linearly with the number of devices. The protocols with privacy protection cannot take into account both authentication efficiency and security while realizing anonymity. Dynamic pseudonym schemes are vulnerable to asynchronous attacks. Therefore, this paper focuses on the authentication between the edge server and device in the IoT and designs a new authentication protocol to realize the privacy protection and improve the efficiency of authentication. Our main contributions can be summarized as follows:(i)
We propose a lightweight anonymous authentication protocol (LAAP) based on elliptic curve cryptography (ECC) to implement security authentication between the servers and devices. Dynamic pseudonym is used to defend against traceable attacks caused by fixed identity identification. Besides, symmetric encryption is used to optimize the server’s search for anonymous device information, and the time complexity is reduced fromOn to O1(ii)
We provide the formal analysis and informal analysis to validate the security of the proposed protocol. The analysis shows that the proposed protocol can satisfy the anonymity and defend against asynchronous attacks. We also perform random oracle models and AVISPA Tool to prove the security of the certification process(iii)
We provide extensive simulation results to testify the authentication efficiency of the proposed protocol. The results indicate that the proposed scheme outperforms the benchmarks in terms of computation overhead, communication overhead, and storage overheadOrganization of this paper is as follows: In Section2, we introduce the preliminaries. In Section 3, we present details of our proposed authentication protocol. Security analysis and performance evaluation are given in Sections 4 and 5, respectively. At last, Section 6 offers our conclusions and potential future works.


## 1.1. Related Work

To implement the security authentication of IoT devices, various protocols and methods were studied. Kalra and Sood in [8] proposed a two-way authentication scheme to realize mutual authentication and meet essential security requirements. Considering the security defects and structural problems of the protocol [8], the improved protocols in [9, 10] were proposed to defend against server emulation attacks. Rostampour et al. then proposed a privacy-preserving anonymous authentication protocol named ECCbAP in [11]; the results indicated that the proposed protocol can achieve the untraceable purpose by traversing the registry. Then, the authors in [12] proposed an authentication protocol based on bilinear pairing to solve the problems of privacy protection and authentication table theft. Subsequently, the enhanced IoT mutual authentication protocol and improved ECC-based authentication protocol were proposed in [13, 14], respectively. To defend against more types of attacks including known temporary information attacks, DoS attacks, Panda and Chattopadhyay proposed an anonymous authentication scheme integrating a password validator in [15]. Further, Bhuarya et al. in [16] proposed an enhanced authentication scheme to defend known session-specific temporary information attack, where the hypertext transfer protocol (HTTP) cookies were used to authenticate clients. However, the large exponential powers employed by these protocols leads to a large amount of computation.The dynamic pseudonym is an effective method to solve traceable problems. A pseudonym ID is used to conduct authentication between client and server and is dynamically updated after completion of authentication. Das et al. first proposed an authentication protocol [17] where dynamic ID technology was used to avoid the risk of ID theft. However, the protocol suffers from smart card theft attacks. Then, Jiang and Das et al. devoted to solving the problem in [18, 19], respectively. Notice when the above schemes are attacked asynchronously, i.e., the attacker blocks the exchange messages of the authentication protocol, and the interaction between the authentication parties is out of sync, such that the protocol cannot work. Thus, Gope et al. in [20–23] studied the authentication scheme based on emergency ID and secret key technology to solve the problem of asynchronous attack. In such schemes, clients and servers share a set of emergency IDs and keys in addition to dynamic pseudonyms. Once the dynamic pseudonyms are out of sync, emergency IDs and keys are used to interact. However, the emergency IDs and keys occupy a large amount of storage space, and once the emergency ID and emergency key are used up, the device must be reregistered. Recently, some researchers devoted to designing grant-free access scheme for M2M communications [24] and used the advanced methods to realize the authentication, e.g., deep learning [25, 26] and blockchain [27, 28]. However, they are not suitable for IoT devices with limited computing overhead.


## 1.2. Motivation and Contribution

To sum up, it can be found that the mentioned authentication protocols based on identity and pseudonym do not consider the privacy protection and cannot resist traceable attacks. For example, if the long-term key is leaked, the attacker can simulate the session key negotiation between the terminal and the server and occupy the position of the legitimate device. As a result, the legitimate device cannot carry out normal session key negotiation. Furthermore, during authentication process, the server needs to traverse the password verifier table to find the relevant registration information, and the search time increases linearly with the number of devices. The protocols with privacy protection cannot take into account both authentication efficiency and security while realizing anonymity. Dynamic pseudonym schemes are vulnerable to asynchronous attacks. Therefore, this paper focuses on the authentication between the edge server and device in the IoT and designs a new authentication protocol to realize the privacy protection and improve the efficiency of authentication. Our main contributions can be summarized as follows:(i)
We propose a lightweight anonymous authentication protocol (LAAP) based on elliptic curve cryptography (ECC) to implement security authentication between the servers and devices. Dynamic pseudonym is used to defend against traceable attacks caused by fixed identity identification. Besides, symmetric encryption is used to optimize the server’s search for anonymous device information, and the time complexity is reduced fromOn to O1(ii)
We provide the formal analysis and informal analysis to validate the security of the proposed protocol. The analysis shows that the proposed protocol can satisfy the anonymity and defend against asynchronous attacks. We also perform random oracle models and AVISPA Tool to prove the security of the certification process(iii)
We provide extensive simulation results to testify the authentication efficiency of the proposed protocol. The results indicate that the proposed scheme outperforms the benchmarks in terms of computation overhead, communication overhead, and storage overheadOrganization of this paper is as follows: In Section2, we introduce the preliminaries. In Section 3, we present details of our proposed authentication protocol. Security analysis and performance evaluation are given in Sections 4 and 5, respectively. At last, Section 6 offers our conclusions and potential future works.


## 2. Preliminaries

In this section, we first introduce the system model and then introduce the related elliptic curve cryptography and the corresponding mathematical problems.


### 2.1. System Model

In this work, we focus on the authentication between cloud server (S) and embedded devices (D) in the IoT shown as Figure 1. The embedded device can be small devices (e.g., environmental sensors, cameras, and smart meters) or large-scale devices (e.g., intelligent vehicles and smart charging piles). The cloud server has powerful computing resources and storage resources, so that it can provide various services for embedded devices. For example, in mobile edge computing networks [29], the device first uploads data to the cloud server and then uses the computing resources to process its data. The cloud server also provides a bootstrap program for the system, enabling authentication to be performed smoothly. Before providing these services, they authenticate between the device and server to ensure legitimate access via wireless channels.Figure 1
System model.


### 2.2. Elliptic Curve Cryptography

The security properties of ECC are mainly based on the intractable problem of discrete logarithms in elliptic curves. Given a prime fieldFp, the elliptic curve point is set Epa,b on the finite field can be expressed as
(1)Eya,b:a,by2=x3+ax+bmodp,x,y∈Fy,4a3+27b2modp≠0∪O,where a,b∈Fp, the prime number pp>3 is the order of the finite field, and O represents the infinity point. The Ellipse Curve Discrete Logarithm Problem (ECDLP) can be described as follows:Definition 1.
ECDLP: letG denote the cyclic group generated by the base point G and the operation rules of Abelian groups on the elliptic curve Eya,b. For a given P,Q∈G, if Q=kP, where k∈Zp∗, k cannot be solved in polynomial time, which is usually used as the private key.Based on the ellipse curve and the ECDLP, the security if the ECC can be described as the Ellipse Curve Computation Diffie-Hellman Problem (ECCDHP), which is defined as follows.Definition 2.
ECCDHP: letG be the cyclic group generated by the base point G and the operation rules of Abelian groups on the elliptic curve Eya,b. For P,Q,R∈G, if Q=xP and R=yP, where x,y∈Z, we have that computing xyP in polynomial time is a hard problem.


### 2.3. Random Oracle Model

Random oracle model (ROM) is proposed by Bellare and Rogaway [30], which made the provable security methodology that was purely theoretical research in the past make significant progress in practical applications. When applying the ROM, the necessary work is to establish a security model that treats different subjects as random oracles (RO). The RO has the following three characteristics: (1) consistency: for the same query, RO will always return the same output; (2) computability: for different queries, RO can obtain results and return them in polynomial time; and (3) uniform distribution: for different queries, the output of RO is evenly distributed in the value space without collision that the output obtained by different queries is always different.To prove the security of the model, it is necessary to establish an attackerA for the model and to provide the attacker with a simulated environment indistinguishable from the actual environment. For A, the complexity and safety of the model boil down to mathematical computational difficulties (e.g., large factorization, ECDLP, and ECCDHP). In ROM, the convention judgement appears as
(1)
Formally define the security of the scheme, assuming that the attacker can destroy the security of the protocol with a nonnegligible probability in polynomial time(2)
The attacker simulates the real environment by querying different random oracles(3)
The way of attacking the attacker and the result boils down to solving a mathematical problemAlthough the ROM methodology cannot be used as absolute proof that the actual solution is safe, it can still be a necessary basic safety test. Thus, this paper adopts it to validate the security of the proposed protocol.


## 2.1. System Model

In this work, we focus on the authentication between cloud server (S) and embedded devices (D) in the IoT shown as Figure 1. The embedded device can be small devices (e.g., environmental sensors, cameras, and smart meters) or large-scale devices (e.g., intelligent vehicles and smart charging piles). The cloud server has powerful computing resources and storage resources, so that it can provide various services for embedded devices. For example, in mobile edge computing networks [29], the device first uploads data to the cloud server and then uses the computing resources to process its data. The cloud server also provides a bootstrap program for the system, enabling authentication to be performed smoothly. Before providing these services, they authenticate between the device and server to ensure legitimate access via wireless channels.Figure 1
System model.


## 2.2. Elliptic Curve Cryptography

The security properties of ECC are mainly based on the intractable problem of discrete logarithms in elliptic curves. Given a prime fieldFp, the elliptic curve point is set Epa,b on the finite field can be expressed as
(1)Eya,b:a,by2=x3+ax+bmodp,x,y∈Fy,4a3+27b2modp≠0∪O,where a,b∈Fp, the prime number pp>3 is the order of the finite field, and O represents the infinity point. The Ellipse Curve Discrete Logarithm Problem (ECDLP) can be described as follows:Definition 1.
ECDLP: letG denote the cyclic group generated by the base point G and the operation rules of Abelian groups on the elliptic curve Eya,b. For a given P,Q∈G, if Q=kP, where k∈Zp∗, k cannot be solved in polynomial time, which is usually used as the private key.Based on the ellipse curve and the ECDLP, the security if the ECC can be described as the Ellipse Curve Computation Diffie-Hellman Problem (ECCDHP), which is defined as follows.Definition 2.
ECCDHP: letG be the cyclic group generated by the base point G and the operation rules of Abelian groups on the elliptic curve Eya,b. For P,Q,R∈G, if Q=xP and R=yP, where x,y∈Z, we have that computing xyP in polynomial time is a hard problem.


## 2.3. Random Oracle Model

Random oracle model (ROM) is proposed by Bellare and Rogaway [30], which made the provable security methodology that was purely theoretical research in the past make significant progress in practical applications. When applying the ROM, the necessary work is to establish a security model that treats different subjects as random oracles (RO). The RO has the following three characteristics: (1) consistency: for the same query, RO will always return the same output; (2) computability: for different queries, RO can obtain results and return them in polynomial time; and (3) uniform distribution: for different queries, the output of RO is evenly distributed in the value space without collision that the output obtained by different queries is always different.To prove the security of the model, it is necessary to establish an attackerA for the model and to provide the attacker with a simulated environment indistinguishable from the actual environment. For A, the complexity and safety of the model boil down to mathematical computational difficulties (e.g., large factorization, ECDLP, and ECCDHP). In ROM, the convention judgement appears as
(1)
Formally define the security of the scheme, assuming that the attacker can destroy the security of the protocol with a nonnegligible probability in polynomial time(2)
The attacker simulates the real environment by querying different random oracles(3)
The way of attacking the attacker and the result boils down to solving a mathematical problemAlthough the ROM methodology cannot be used as absolute proof that the actual solution is safe, it can still be a necessary basic safety test. Thus, this paper adopts it to validate the security of the proposed protocol.


## 3. Design of the Authentication Protocol

In this section, we introduce the proposed LAAP protocol including three phases, i.e., initialization phase, registration phase, and authentication phase. A summary of the notations used in this article is provided in Table1.Table 1
List of the related notations.
NotationDescriptionDi,IDiThei device and its device IDSCloud serverxCloud server symmetric keyPKS,KServer public key, private keyNIDDevice pseudonym identificationNID′Updated pseudonym identificationDIDDevice real identityDID′Device updated real identitySyncServer sync valueN1,N2,RiRandom numberGCyclic additive group of orderqSiDevice-side hash chain valueSiiServer-side hash chain valuehOne-way hash functionConnect operationSKSession key


### 3.1. Initialization Phase

Before authentication, the server needs to perform necessary parameter initialization operations. Initialization parameters are divided into public parameters and private parameters. The server selects an elliptic curveE based on the finite prime field Fp and selects the additive group of curve E of the order q. Then, the public key of the server PKS can be calculated as PKS=K×G, where KK∈Zq∗ is the private key and G is the generator of the group G. The server also needs to select a suitable one-way hash function h:0,1∗⟶0,1lh, where the input is any length binary string and the output is a binary string of fixed length lh. The server generates a random key x as a symmetric encryption key and selects an appropriate symmetric encryption algorithm as the basic algorithm for device identification update. The server publishes the parameters G,PKS,G,h as public parameters and stores x,K as private parameters.


### 3.2. Registration Phase

Before starting key negotiation, the device first needs to complete the registration. The LAAP protocol can ensure that the registration is completed by the public channel, and check whether the message responded by the server is legal. The registration process can be divided into three steps described as Figure2. In the following, we will detail the three steps.Step 1.
The deviceD first selects an unique ID, which is only known by the device. Then, the device generates a random number N1 to randomize its ID and calculates PID,Z1,Z2 and PPID as PID=hIDN1,Z1=N1×G,Z2=N1×PKS and PPID=PID⊕Z2, respectively. Finally, the device sends the message Z1,PPID to the server through the public channel.Step 2.
After receiving the registration informationZ1,PPID from D, server S uses the key K to restore the data, where Z2∗ and PID are calculated according to Z2∗=Z1×K,PID=PPID⊕Z2∗, respectively. After restoring PID, Ti is generated based on the device registration identity as Ti=hRiPIDhK, which is used to calculate the identity information for each authentication of the device. Otherwise, the server also generates a new identity PIDnew=hPIDRi for the device as the identity of the authentication stage. The server will save two IDs for each device, i.e., PIDnew and PIDold, where PIDnew is the new device ID and PIDold is the old ID of the previous session. Then, the hash value of PID is used as the initial value of the hash chain, which will be updated during each session key negotiation process.Figure 2
Illustration of registration phase of LAAP.Subsequently, the server uses the hash value of the keyK to encrypt Ti and Si and stores the results in its database. After that, the server calculates the message of the response device as Z3=NIDPID⊕Si and Z4=TiPID⊕Si. Finally, the server sends Z3,Z4 to the device through the public channel and stores PIDnew,PIDold,Ui,Xi,Sync as the registration information corresponding to the device.Step 3.
After receiving the messageZ3,Z4 from the server, the device uses the initial value of the hash chain to restore and verify the data as NIDPID′=Z3⊕Si,TiPID′=Z4⊕Si. By splitting the data, the device verifies whether the decrypted PID′ is the same as the PID saved by itself. If they are the same, the device confirms that the message was sent by the server and stores NID,Ti as the registration information for subsequent identity authentication and key negotiation.


### 3.3. Authentication Phase

When the device wants to upload data or access the server, the device and server need to complete identity authentication and key negotiation. The authentication process can be divided into four steps described as Figure3. In the following, we will introduce the four steps for details.Step 1.
DeviceD first generates a random number N1 and calculates P1=N1×G, CKi′=hTiSi×G, and Ai=CKi′×N1, where CKi′ and Ai are temporary values generated by the synchronization hash chain and the identity information in the registration phase. Then, the verification message P2 is generated as P2=hAiSiP1. On the one hand, it can prevent message tampering, and on the other hand, it can verify whether the identity is legitimate. Finally, the device sends the message P1,P2,NID to the server for authentication.Step 2.
After receiving the messageP1,P2,NID, S restores the identity information DID based on the symmetric key x. If the recovery is successful, S can judge the recovery based on the matching information of the database; otherwise, terminate the session. When DID=PIDnew, the server updates the synchronization hash value as Sii=hSiiSync and reconstructs the authentication temporary value for this session as CKi=hTiSii,Ai′=CKi×P1. Then, S calculates the verification message P2′ as P2′=hAi′SiiP1. If P2≠P2′, it means that the message has been tampered with and the session is terminated. Otherwise, S generates a random number N2 and a new identity for D as DID′=hDIDN2. Finally, S calculates the verification messages as P3=NID′⊕Sii,P4=hNID′SiiAi′ and sends them to D.Step 3.
After receiving the messageP3,P4, D decrypts and verifies the new ID P4′=hNID′SiAi where NID′=Si⊕P3. If P4≠P4′, the message verification fails, and the session is terminated; otherwise, D calculates the negotiated session key and the verification message as SK=hAiNID′NID,P5=hSKNID′NID. Finally, the device sends the message P5 to the server.Step 4.
After receiving the messageP5, S can calculate the negotiated session key and verify the message as SK=hAi′PIDnewPIDold and P5′=hSKPIDnewPIDold, respectively. If P5≠P5′,the server terminate the session, otherwise, the session key negotiation is successful.Figure 3
Illustration of authentication phase of LAAP.


## 3.1. Initialization Phase

Before authentication, the server needs to perform necessary parameter initialization operations. Initialization parameters are divided into public parameters and private parameters. The server selects an elliptic curveE based on the finite prime field Fp and selects the additive group of curve E of the order q. Then, the public key of the server PKS can be calculated as PKS=K×G, where KK∈Zq∗ is the private key and G is the generator of the group G. The server also needs to select a suitable one-way hash function h:0,1∗⟶0,1lh, where the input is any length binary string and the output is a binary string of fixed length lh. The server generates a random key x as a symmetric encryption key and selects an appropriate symmetric encryption algorithm as the basic algorithm for device identification update. The server publishes the parameters G,PKS,G,h as public parameters and stores x,K as private parameters.


## 3.2. Registration Phase

Before starting key negotiation, the device first needs to complete the registration. The LAAP protocol can ensure that the registration is completed by the public channel, and check whether the message responded by the server is legal. The registration process can be divided into three steps described as Figure2. In the following, we will detail the three steps.Step 1.
The deviceD first selects an unique ID, which is only known by the device. Then, the device generates a random number N1 to randomize its ID and calculates PID,Z1,Z2 and PPID as PID=hIDN1,Z1=N1×G,Z2=N1×PKS and PPID=PID⊕Z2, respectively. Finally, the device sends the message Z1,PPID to the server through the public channel.Step 2.
After receiving the registration informationZ1,PPID from D, server S uses the key K to restore the data, where Z2∗ and PID are calculated according to Z2∗=Z1×K,PID=PPID⊕Z2∗, respectively. After restoring PID, Ti is generated based on the device registration identity as Ti=hRiPIDhK, which is used to calculate the identity information for each authentication of the device. Otherwise, the server also generates a new identity PIDnew=hPIDRi for the device as the identity of the authentication stage. The server will save two IDs for each device, i.e., PIDnew and PIDold, where PIDnew is the new device ID and PIDold is the old ID of the previous session. Then, the hash value of PID is used as the initial value of the hash chain, which will be updated during each session key negotiation process.Figure 2
Illustration of registration phase of LAAP.Subsequently, the server uses the hash value of the keyK to encrypt Ti and Si and stores the results in its database. After that, the server calculates the message of the response device as Z3=NIDPID⊕Si and Z4=TiPID⊕Si. Finally, the server sends Z3,Z4 to the device through the public channel and stores PIDnew,PIDold,Ui,Xi,Sync as the registration information corresponding to the device.Step 3.
After receiving the messageZ3,Z4 from the server, the device uses the initial value of the hash chain to restore and verify the data as NIDPID′=Z3⊕Si,TiPID′=Z4⊕Si. By splitting the data, the device verifies whether the decrypted PID′ is the same as the PID saved by itself. If they are the same, the device confirms that the message was sent by the server and stores NID,Ti as the registration information for subsequent identity authentication and key negotiation.


## 3.3. Authentication Phase

When the device wants to upload data or access the server, the device and server need to complete identity authentication and key negotiation. The authentication process can be divided into four steps described as Figure3. In the following, we will introduce the four steps for details.Step 1.
DeviceD first generates a random number N1 and calculates P1=N1×G, CKi′=hTiSi×G, and Ai=CKi′×N1, where CKi′ and Ai are temporary values generated by the synchronization hash chain and the identity information in the registration phase. Then, the verification message P2 is generated as P2=hAiSiP1. On the one hand, it can prevent message tampering, and on the other hand, it can verify whether the identity is legitimate. Finally, the device sends the message P1,P2,NID to the server for authentication.Step 2.
After receiving the messageP1,P2,NID, S restores the identity information DID based on the symmetric key x. If the recovery is successful, S can judge the recovery based on the matching information of the database; otherwise, terminate the session. When DID=PIDnew, the server updates the synchronization hash value as Sii=hSiiSync and reconstructs the authentication temporary value for this session as CKi=hTiSii,Ai′=CKi×P1. Then, S calculates the verification message P2′ as P2′=hAi′SiiP1. If P2≠P2′, it means that the message has been tampered with and the session is terminated. Otherwise, S generates a random number N2 and a new identity for D as DID′=hDIDN2. Finally, S calculates the verification messages as P3=NID′⊕Sii,P4=hNID′SiiAi′ and sends them to D.Step 3.
After receiving the messageP3,P4, D decrypts and verifies the new ID P4′=hNID′SiAi where NID′=Si⊕P3. If P4≠P4′, the message verification fails, and the session is terminated; otherwise, D calculates the negotiated session key and the verification message as SK=hAiNID′NID,P5=hSKNID′NID. Finally, the device sends the message P5 to the server.Step 4.
After receiving the messageP5, S can calculate the negotiated session key and verify the message as SK=hAi′PIDnewPIDold and P5′=hSKPIDnewPIDold, respectively. If P5≠P5′,the server terminate the session, otherwise, the session key negotiation is successful.Figure 3
Illustration of authentication phase of LAAP.


## 4. Security Analysis

In this section, we provide the formal analysis and informal analysis to validate the security of the proposed protocol.


### 4.1. Formal Security Proof

For the formal analysis, we first adopts the widely accepted ROM [30] to verify the security of the proposed protocol.


#### 4.1.1. Formal Security Proof with ROM

The extended RO is described as follows:TestIDDi,NIDi,OIDi is used to query the real identity information of the device, where NIDi and OIDi represent the identity after session key negotiation and the identity before session key negotiation, respectively. CorruptDi,a is used to query the secret information of the device and simulate the attack of the device being stolen.There are two participantsΠ in this work, i.e., server S and the embedded device D. Each participant has multiple instances (i.e., ROs). Let Di and Si represent the i-th instance of them, respectively; DIDi and SIDi represent the identity of Di and Si that are used to negotiate the session key, respectively; NIDi and OIDi indicate the updated ID and the preupdated ID of D, respectively; HDi and HSi, respectively, represent the hash chain status of D and S; SKij represents the negotiated key for the j-th time.If the instanceSi receives all the expected messages according to the predetermined steps, the instance enters the accepting state denoted as AccΠi=1. In this protocol, the parties negotiating the secure session key should meet the following conditions: (1) both S and D enter the receiving state, i.e., AccDi=AccSi=1; (2) D updates the identity, DIDi=NIDi; (3) the identities of S and D are not empty, i.e., DIDi≠null, SIDi≠nullIn the ROM, an attacker can simulate the attack by querying the RO. The included query is defined as follows:Passive attackExecuteDi,Si: the attacker can query the oracle to obtain the messages exchanged between Di and Si, giving the attacker the ability to eavesdrop on the channel.Active attackSendΠ,m: the attacker can interact with any participant by querying the oracle machine, and the oracle machine processes the message. If the message is valid, the oracle machine returns the processing result of message m; if the message is invalid, the oracle machine ignores the message.RevealΠ: the attacker can obtain the session key of any participant by querying the oracle, and this query will only return the held key if the participant actually holds the session key. When an attacker queries the random oracle, the correct session key will be returned only if Π is accepted; otherwise, a random element in the state space will be returned.CorruptDi,a: when a=1, the hash chain value of Di is fed back during the query. If the hash chain value is invalid, the random element in the state space is returned. When a=2, the query information is the registration information Ti of Di. If the registration information Ti is invalid, the random element in the state space is returned.TestIDDi,NIDi,OIDi: the attacker can obtain the real identity of the device by querying the oracle. If the sent message Di is accepted, it will return the real identity of the device; otherwise, it will return a random element in the state space. This oracle is used to test the anonymity of the protocol.TestSKΠ: when the attacker queries the oracle, the RO throws an unbiased coin b, and the result is used to determine whether the query returns the correct result. If b=0, it returns a random element in the state space; if b=1, and the participant holds the session key, return the correct session key; otherwise return it. The oracle tests the security of the negotiated session key, where the query can only be executed once.Semantic security for session keys. In the defined ROM, attackerA can query the session key through RevealΠ or TestSKΠ, and random elements in the state space will be returned during the query process; query through TestIDDi,NIDi,OIDi The real identity of the device. A needs to distinguish between random elements and real information. The goal of A is to guess the real information. At the end of the experiment, the attacker returns a guess bit c∗. If c∗=c, then A wins the game event, which destroys the security of the protocol. Succi denotes that A wins the ith experiment, and P denotes the constructed LAAP protocol. More precisely, the advantage of A overcoming the semantic security of the protocol is Advp=2·PrSucc0−1, if the experiment ends, the probability of obtaining A attack success is negligible, indicating that the protocol is semantically secure.Based on the above definitions, we have the following theorem which proves the security of the proposed protocol.Theorem 3.
LetAdvP denote the advantage of an adversary A to break through the semantic security of the proposed protocol P, and let AdvExSE denote the advantage of A in cracking the ciphertext symmetric encrypted with the server key pair within a probability polynomial, and let AdvEpECDLP denote the advantage of solving the ECDLP problem of Ep in any polynomial time
(2)AdvP≤2qs+qe2+2qt22lh+2AdvEpECDLPt+2AdvExSEt,where Ep and Ex are the elliptic curve group and the symmetric encryption algorithm, respectively, and qs, qe, and qt denote the times that attacker A executes the queries SendΠ,m, ExecuteDi,Si, and TestIDDi,a, respectivelyProof.
LetPrSucci denote the probability that A wins in the i-th experiment. The contribution of the i+1-th experiment to the probability of A winning can be expressed PrSucci−PrSucci+1. The proof process can be described as the following five different experiments.
Experiment 1. This experiment corresponds to a real attack in the ROM. WhenA implements a real attack on the protocol P under the ROM model, we have
(3)AdvP=2·PrSucc0−1.
Experiment 2. This experiment is used to simulate an eavesdropping attack of an adversaryA. We know SK=hAiNID′NID in the protocol, where Ai is calculated by the embedded device through CKi and random number N1, and NID′ is encrypted by the server with the secret key x. Even if intercepting all parameters transmitted during the authentication phase, A still cannot get it any information. Therefore implementing an eavesdropping attack cannot increase the probability of A winning, and we can obtain
(4)PrSucc0=PrSucc1.
Experiment 3. This experiment is used to simulate all possible hash collisions in the authentication phase based on Experiment 2.A tries to find hash collisions, and if the same output is produced for different inputs, the game ends. According to the birthday paradox (the number of collision tests for a hash table of N bit length is not 2N but only N), we have
(5)PrSucc2−PrSucc1≤qs+qe22lh,where qs and qe represent the times that attacker A queries SendΠ,m and ExecuteDi,Si, respectively.
Experiment 4. Based on Experiment 3, attackerA queries the device’s secret information Ti and hash chain value Si by adding TestIDDi,NIDi,OIDi. If A successfully obtains the information, the probability that A wins the experiment is
(6)PrSucc2−PrSucc1≤qt22lh,where qt represents the times that the attacker A queries TestIDDi,a.
Experiment 5. Based on Experiment 4, the experiment adds thatA can tamper with the authentication information and make legitimate participants believe the tampered message, i.e., A can eavesdrop on the message and can make Hash collision. The following two cases will occur: (1) A tampers with message P1, and (2) A tampers with message P3.
Case 1. In this case, after tampering withP1, the adversary needs to solve how to correspond to the verification message P2. For this reason, the adversary needs to solve the ECDLP problem, and guess N1 and CKi, (i.e., 2AdvPECDLPt), so that it can guess CKi. Besides, A still needs to solve a symmetric key problem to generate legal P5, i.e., ADVExSEt. Overall, we have
(7)PrSucc4Case1≤2AdvEpECDLPt+AdvExSEt.
Case 2. In this case,A tampers with P3 to impersonate the server. Assuming that A has obtained the synchronization value Si shared by the device and the server, A still needs to solve the symmetric key decryption problem, i.e., AdvExSEt. Similarly, if A has decrypted the current symmetric key problem, A still needs to solve the ECDLP problem to obtain the legal Ai, i.e., AdvEpECDLPt. Thus, we have
(8)PrSucc4Case2≤AdvEpECDLPt+AdvExSEt.
In summary, the probability that the adversaryA wins in Experiment 5 is
(9)PrSucc4−PrSucc3≤AdvFpECDLPt+AdvExSEt.
All random predictions are simulated in the above four experiments. The results indicate thatA has no advantage in guessing the bit c, and the only way to pass the test is to perform TestSKΠ query guessing, i.e.,
(10)PrSucc4=12.
Using the triangle inequality, we can obtain(11)12AdvP=PrSucc0−PrSucc4.
Based on (3)–(8), we have
(12)PrSucc0−PrSucc4≤qs+qe22lh+qt22lh+AdvPECDLPt+AdvExSEt.
Submitting (12) into (11), we can obtain (2).Remark 4.
This result indicates that the adversaryA has no extra advantage to win the experiment and the proposed scheme is secure.


#### 4.1.2. Formal Security Proof with AVISPA Tool

In this part, the AVISPA verification tool is used to verify the security of the LAAP protocol. The experimental environment is Oracle VM VirtualBox, SPAN-Ubuntu10.10-light. The HLPSL language description of the protocol is divided into the following five dimensions.Role attributes:D and S are two agents, Hash and Mutli are two hash functions, Kab is a symmetric key, and Snd and RCV are the communication channels between the client and the outside world. The local variables defined are the same as the protocol description, as shown in Figure 4(a). The modeling of the server is similar to that of the client, as shown in Figure 4(b).Figure 4
Role attributes of the clientD and the serve S.
(a)
Role attribute ofD(b)
Role attribute ofSRole conversion process: the conversion process ofD in LAAP is divided into three stages: register1 means that D starts to register and sends registration information to S; register2 means that D receives the response from S, conducts authentication calculation, and initiates an authentication request; authentication1 indicates that D receives the response from S and completes the final authentication process, as shown in Figure 5(a). Similarly, the conversion process of S is also divided into three stages: register indicates that S requests the registration information of D; authentication1 means that S receives the authentication request of D and performs verification and response; authentication2 means that S receives the response of D and completes the final authentication process, as shown in Figure 5(b).Figure 5
Role change process, session attributes, and environmental attributes.
(a)
Role change process of D(b)
Role change process of S(c)
Session attributes(d)
Environmental attributesSession attributes: the modeling of LAAP session attributes defines the rules that the communicating entities follow. The definition of basic attributes includes the role agentsD and S, hash functions Hash and Multi, symmetric key Qi, and communication channels SND and RCV as shown in Figure 5(c).Environmental attributes: the definition content of LAAP environment includes the communication channel of the communication entity, communication entity (includingd, s, and i), security target constant, and session combination, as shown in Figure 5(d).Safety goals: the security goal describes the secret information “secrecy_of” and the authentication quantity “authentication_o” of the communication entity defined in the protocol shown in Figure6.Figure 6
Description of the safety goals.The OFMC simulation results are shown in Figure6, and the ATSE simulation results are shown in Figure 6. From Figure 7, we can see that the LAAP realizes two-way authentication while resisting man-in-the-middle attacks and replay attacks, which proves the security of the protocol.Figure 7
Verification results of security with AVISPA.
(a)
OFMC backend simulation results(b)
ATSE backend simulation results


### 4.2. Informal Security Analysis

Informal security analysis mainly consists of two parts, i.e., basic function security and common attack defense. Basic functional security includes mutual authentication and device anonymity. Common attacks resistance mainly includes traceable attack defense, asynchronous attack defense, DoS attack defense, replay attack defense, and simulation attack defense.Mutual authentication. In the LAAP protocol, serverS authenticates the legal identity of device D based on the message P1,P2,NID and then restores the identity of the device with NID. This precess is performed through symmetric encryption. If S gets a string of garbled characters after decrypting NID or cannot find matching information in the verification table, S will discard the authentication message. After successfully decrypting NID and obtaining the device’s identity DID, S verifies the authenticity of the device with CKi=hTiSii,P2′=hAi′SiiP1. If P2=P2′, the verification is passed. In the response message P3,P4, P3 contains the new identity of the device, which is encrypted by the hash chain value synchronized by both parties, and P4 contains the authentication information Ai. Notice that only valid S can calculate Ai′. Thus, if the P4′ calculated by the device is the same as the received P4, D can confirm the legal identity of SDevice anonymity. Device anonymity means that attackerA cannot obtain any identifying information about the participants by listening to the messages in the channel. In the LAAP, the method of dynamic pseudonym and synchronous hash chain are used to solve the anonymity of the device. Notice that the identity identification NID is dynamically updated in the second phase of device authentication so that the identity identifications are different at different session stages. Under the Deolv-Yao attack model [31], A is completely unable to distinguish the attribution of different sessions. Therefore, the proposed protocol satisfies the anonymity requirement of the device.Traceable attack defense. Traceable attack means that attackerA can identify the belonging of messages by listening to the information in the channel, so as to carry out specific analysis to undermine the security of the protocol. Recall that the LAAP protocol used the dynamic pseudonym. Thus, after each successful session key negotiation, the device identity is updated. That is, the NIDi sent in the i-th session is completely different from the NIDi+1 sent in the i+1-th session. Therefore, A cannot determine which communication entity the session message belongs to and also cannot track the session information of specific equipment.Asynchronous attack defense. An asynchronous attack intercepts message transmission to make protocol participants lose synchronization. As a result, the protocol cannot be executed correctly, thus destroying the protocol. According to the LAAP, the messages transmitted on the public channel includesP1,P2,NID, P3,P4, and P5. There are two messages related to synchronization information, i.e., the initial authentication message P1,P2,NID and the response message P3,P4 sent by S and D, respectively. For attacker A, intercepting message P1,P2,NID has no effect on the synchronization of the protocol. Thus, we only consider the following two cases.Case 1 (A intercepts the message).
S has updated the device ID as PIDnew=DIDi+1,PIDold=DIDi because S has already processed the message i. At this time, due to the information interception, the identity identifier DIDi of D is the corresponding NIDi. When the timer of D expires, D will regenerate the random number to reauthenticate and send the message P1i,P2i,NIDi to S. We can see that PIDold=DIDi, and S will determine that D is out of synchronization, and the current hash value is directly used for authentication.Case 2 (A intercepts the message P5).
The system status is thatS updated the device ID, and D updated the device ID and hash chain value. After P5 is intercepted, the hash chain value of the protocol participant S is synchronously behind D. When the timer of device D expires, D resends the authentication message P1i+1,P2i+1,NIDi+1, and PIDnew=DIDi+1. the hash chain value will be updated, and Sync will be used in the update process. Therefore, D and S will resume synchronization.DoS attacks defense. DoS attack means that attackerA sends a large amount of invalid authentication information to the server, which consumes the computing resources of the server and makes the server unable to provide services normally. In the protocols in [11, 15], there is a way to find information about related devices by traversing the password check table or the local registry. Thus, their time complexity is On. When there are enough registrations, even if most of the devices are offline, the server will go through all the devices during the authentication process. The proposed LAAP protocol combine the dynamic pseudonym with symmetric encryption, and the time complexity is reduced from On to O1. So, the proposed protocol has a high authentication efficiency and can resist DoS attacks.Replay attacks defense. Replay attack means that the attacker resends the message sent in the history negotiation stage to the server, thus achieving the purpose of spoofing. In LAAP, the messages transmitted by the public channel consistP1,P2,NID,P3,P4, and P5. Let the message sent by the device in the i-th session be P1i,P2i,NIDi, the message sent by the server be P3i,P4i, and the response message from the device be P5i. Thus, there would be the following three cases.Case 1 (A replays the message P1i,P2i,NIDi).
We will analyze it from two subcases. In subcase 1, the attacker launches a replay attack in the middle of thei-th and i+1-th key negotiation at the device side. Note that the device has not performed the i+1-th key negotiation. Because the server will store the ith device identity, the server will find PIDold=DxNIDi in the authentication table and will consider that device is out of asynchrony. So in the next step of message verification, the server will calculate Sync=hAi′ and classify the message as a replay attack and discard the session. In subcase 2, A uses the device history negotiation information P1i−n,P2i−n,NIDi−n, where n∈0,i−1): After receiving P1i−n,P2i−n,NIDi−n, the server uses key symmetric decryption to get the i−n−1-th device identity based on NIDi−n. But the server cannot find the relevant information in the database, and it will discard the session.Case 2 (A replay the message P3i,P4i).
Similarly, we will analyze it from two subcases. Subcase 1 is similar to the above subcase. After receivingP3i,P4i, the device will decrypt P3i to obtain the new device identifier NIDi′. At this time, the hash chain value at the device has been updated, and P4i′ computed by the device is different from the received P4. So, the device will terminate the session. For subcase 2, after receiving the history information P3i−n,P4i−n (where n∈0,i−1), the device will decrypt P3i−n to get the identity NIDi−n+1. However, because the hash chain value has been updated several times, NIDi−n+1′ obtained by decrypting P4i−n′ is different from P4i−n. Thus, the device will terminate the session.Case 3 (A replay the historical message P5i).
The server will use the new authentication information and message to calculate as follows:(13)SK=hAi_new′NIDnew′NIDnew,P5_new′=hSKnewSKnew.We can find thatP5_new′ is different from P5i. Thus, the session key negotiation cannot be successful, and the server will discard the session.Based on the analysis of the above three cases, we proof that the proposed protocol can resist the replay attacks.Simulation attack defense. An emulation attack means that the attacker tampers authentication information to establish session keys on the simulated device or server. An attackerA can tamper with or send historical authentication messages to spoof the device or the server based on the intercepted authentication messages.For messagesP1,P2,NID, A has no access to the registration information Ti and the synchronization hash value of the device, so it cannot obtain the legitimate P2 to spoof S. If A replays the historical messages, see the above analysis for details. For messages P3,P4, A cannot know symmetric encryption key x of S and the authentication message Ai′ generated in this session, so it cannot compute the legitimate P3 and P4. If A replays the historical message, the session is terminated due to authentication failure. For message P5, A cannot know the authentication message Ai′ of this session, so that it cannot compute P5. If A replays the history message, the authentication will fail, and S terminates the session. In summary, the proposed protocol can resist the simulation attacks.We provide Table2 to show the comparison of security performance between LAAP and the benchmarks. The dimension of comparison is based on the basic functional security and common attack resistance described in the above. In Table 2, where “Yes” (resp. “No”) indicate that the protocol can (cannot) support the security feature, and “—” indicates that the protocol does not involve this security feature. From Table 2, we can see that the proposed LAAP protocol can resist more security attacks.Table 2
Comparison of security performance.
IndexS1S2S3S4S5S6S7BenchCwsNoNoNoNoYesNo—WangYesNoYesNoYesNo—PandaYesYesYesYesYesNo—RostampourYesYesYesYesNoYes—BhuaryaYesYesYesYesYesNo—LAAPYesYesYesYesYesYesYesS1-S7 are the index of the mutual authentication, device anonymity, traceable attack defense, asynchronous attack defense, DoS attacks defense, replay attacks defense, and simulation attack defense, respectively.


## 4.1. Formal Security Proof

For the formal analysis, we first adopts the widely accepted ROM [30] to verify the security of the proposed protocol.


### 4.1.1. Formal Security Proof with ROM

The extended RO is described as follows:TestIDDi,NIDi,OIDi is used to query the real identity information of the device, where NIDi and OIDi represent the identity after session key negotiation and the identity before session key negotiation, respectively. CorruptDi,a is used to query the secret information of the device and simulate the attack of the device being stolen.There are two participantsΠ in this work, i.e., server S and the embedded device D. Each participant has multiple instances (i.e., ROs). Let Di and Si represent the i-th instance of them, respectively; DIDi and SIDi represent the identity of Di and Si that are used to negotiate the session key, respectively; NIDi and OIDi indicate the updated ID and the preupdated ID of D, respectively; HDi and HSi, respectively, represent the hash chain status of D and S; SKij represents the negotiated key for the j-th time.If the instanceSi receives all the expected messages according to the predetermined steps, the instance enters the accepting state denoted as AccΠi=1. In this protocol, the parties negotiating the secure session key should meet the following conditions: (1) both S and D enter the receiving state, i.e., AccDi=AccSi=1; (2) D updates the identity, DIDi=NIDi; (3) the identities of S and D are not empty, i.e., DIDi≠null, SIDi≠nullIn the ROM, an attacker can simulate the attack by querying the RO. The included query is defined as follows:Passive attackExecuteDi,Si: the attacker can query the oracle to obtain the messages exchanged between Di and Si, giving the attacker the ability to eavesdrop on the channel.Active attackSendΠ,m: the attacker can interact with any participant by querying the oracle machine, and the oracle machine processes the message. If the message is valid, the oracle machine returns the processing result of message m; if the message is invalid, the oracle machine ignores the message.RevealΠ: the attacker can obtain the session key of any participant by querying the oracle, and this query will only return the held key if the participant actually holds the session key. When an attacker queries the random oracle, the correct session key will be returned only if Π is accepted; otherwise, a random element in the state space will be returned.CorruptDi,a: when a=1, the hash chain value of Di is fed back during the query. If the hash chain value is invalid, the random element in the state space is returned. When a=2, the query information is the registration information Ti of Di. If the registration information Ti is invalid, the random element in the state space is returned.TestIDDi,NIDi,OIDi: the attacker can obtain the real identity of the device by querying the oracle. If the sent message Di is accepted, it will return the real identity of the device; otherwise, it will return a random element in the state space. This oracle is used to test the anonymity of the protocol.TestSKΠ: when the attacker queries the oracle, the RO throws an unbiased coin b, and the result is used to determine whether the query returns the correct result. If b=0, it returns a random element in the state space; if b=1, and the participant holds the session key, return the correct session key; otherwise return it. The oracle tests the security of the negotiated session key, where the query can only be executed once.Semantic security for session keys. In the defined ROM, attackerA can query the session key through RevealΠ or TestSKΠ, and random elements in the state space will be returned during the query process; query through TestIDDi,NIDi,OIDi The real identity of the device. A needs to distinguish between random elements and real information. The goal of A is to guess the real information. At the end of the experiment, the attacker returns a guess bit c∗. If c∗=c, then A wins the game event, which destroys the security of the protocol. Succi denotes that A wins the ith experiment, and P denotes the constructed LAAP protocol. More precisely, the advantage of A overcoming the semantic security of the protocol is Advp=2·PrSucc0−1, if the experiment ends, the probability of obtaining A attack success is negligible, indicating that the protocol is semantically secure.Based on the above definitions, we have the following theorem which proves the security of the proposed protocol.Theorem 3.
LetAdvP denote the advantage of an adversary A to break through the semantic security of the proposed protocol P, and let AdvExSE denote the advantage of A in cracking the ciphertext symmetric encrypted with the server key pair within a probability polynomial, and let AdvEpECDLP denote the advantage of solving the ECDLP problem of Ep in any polynomial time
(2)AdvP≤2qs+qe2+2qt22lh+2AdvEpECDLPt+2AdvExSEt,where Ep and Ex are the elliptic curve group and the symmetric encryption algorithm, respectively, and qs, qe, and qt denote the times that attacker A executes the queries SendΠ,m, ExecuteDi,Si, and TestIDDi,a, respectivelyProof.
LetPrSucci denote the probability that A wins in the i-th experiment. The contribution of the i+1-th experiment to the probability of A winning can be expressed PrSucci−PrSucci+1. The proof process can be described as the following five different experiments.
Experiment 1. This experiment corresponds to a real attack in the ROM. WhenA implements a real attack on the protocol P under the ROM model, we have
(3)AdvP=2·PrSucc0−1.
Experiment 2. This experiment is used to simulate an eavesdropping attack of an adversaryA. We know SK=hAiNID′NID in the protocol, where Ai is calculated by the embedded device through CKi and random number N1, and NID′ is encrypted by the server with the secret key x. Even if intercepting all parameters transmitted during the authentication phase, A still cannot get it any information. Therefore implementing an eavesdropping attack cannot increase the probability of A winning, and we can obtain
(4)PrSucc0=PrSucc1.
Experiment 3. This experiment is used to simulate all possible hash collisions in the authentication phase based on Experiment 2.A tries to find hash collisions, and if the same output is produced for different inputs, the game ends. According to the birthday paradox (the number of collision tests for a hash table of N bit length is not 2N but only N), we have
(5)PrSucc2−PrSucc1≤qs+qe22lh,where qs and qe represent the times that attacker A queries SendΠ,m and ExecuteDi,Si, respectively.
Experiment 4. Based on Experiment 3, attackerA queries the device’s secret information Ti and hash chain value Si by adding TestIDDi,NIDi,OIDi. If A successfully obtains the information, the probability that A wins the experiment is
(6)PrSucc2−PrSucc1≤qt22lh,where qt represents the times that the attacker A queries TestIDDi,a.
Experiment 5. Based on Experiment 4, the experiment adds thatA can tamper with the authentication information and make legitimate participants believe the tampered message, i.e., A can eavesdrop on the message and can make Hash collision. The following two cases will occur: (1) A tampers with message P1, and (2) A tampers with message P3.
Case 1. In this case, after tampering withP1, the adversary needs to solve how to correspond to the verification message P2. For this reason, the adversary needs to solve the ECDLP problem, and guess N1 and CKi, (i.e., 2AdvPECDLPt), so that it can guess CKi. Besides, A still needs to solve a symmetric key problem to generate legal P5, i.e., ADVExSEt. Overall, we have
(7)PrSucc4Case1≤2AdvEpECDLPt+AdvExSEt.
Case 2. In this case,A tampers with P3 to impersonate the server. Assuming that A has obtained the synchronization value Si shared by the device and the server, A still needs to solve the symmetric key decryption problem, i.e., AdvExSEt. Similarly, if A has decrypted the current symmetric key problem, A still needs to solve the ECDLP problem to obtain the legal Ai, i.e., AdvEpECDLPt. Thus, we have
(8)PrSucc4Case2≤AdvEpECDLPt+AdvExSEt.
In summary, the probability that the adversaryA wins in Experiment 5 is
(9)PrSucc4−PrSucc3≤AdvFpECDLPt+AdvExSEt.
All random predictions are simulated in the above four experiments. The results indicate thatA has no advantage in guessing the bit c, and the only way to pass the test is to perform TestSKΠ query guessing, i.e.,
(10)PrSucc4=12.
Using the triangle inequality, we can obtain(11)12AdvP=PrSucc0−PrSucc4.
Based on (3)–(8), we have
(12)PrSucc0−PrSucc4≤qs+qe22lh+qt22lh+AdvPECDLPt+AdvExSEt.
Submitting (12) into (11), we can obtain (2).Remark 4.
This result indicates that the adversaryA has no extra advantage to win the experiment and the proposed scheme is secure.


### 4.1.2. Formal Security Proof with AVISPA Tool

In this part, the AVISPA verification tool is used to verify the security of the LAAP protocol. The experimental environment is Oracle VM VirtualBox, SPAN-Ubuntu10.10-light. The HLPSL language description of the protocol is divided into the following five dimensions.Role attributes:D and S are two agents, Hash and Mutli are two hash functions, Kab is a symmetric key, and Snd and RCV are the communication channels between the client and the outside world. The local variables defined are the same as the protocol description, as shown in Figure 4(a). The modeling of the server is similar to that of the client, as shown in Figure 4(b).Figure 4
Role attributes of the clientD and the serve S.
(a)
Role attribute ofD(b)
Role attribute ofSRole conversion process: the conversion process ofD in LAAP is divided into three stages: register1 means that D starts to register and sends registration information to S; register2 means that D receives the response from S, conducts authentication calculation, and initiates an authentication request; authentication1 indicates that D receives the response from S and completes the final authentication process, as shown in Figure 5(a). Similarly, the conversion process of S is also divided into three stages: register indicates that S requests the registration information of D; authentication1 means that S receives the authentication request of D and performs verification and response; authentication2 means that S receives the response of D and completes the final authentication process, as shown in Figure 5(b).Figure 5
Role change process, session attributes, and environmental attributes.
(a)
Role change process of D(b)
Role change process of S(c)
Session attributes(d)
Environmental attributesSession attributes: the modeling of LAAP session attributes defines the rules that the communicating entities follow. The definition of basic attributes includes the role agentsD and S, hash functions Hash and Multi, symmetric key Qi, and communication channels SND and RCV as shown in Figure 5(c).Environmental attributes: the definition content of LAAP environment includes the communication channel of the communication entity, communication entity (includingd, s, and i), security target constant, and session combination, as shown in Figure 5(d).Safety goals: the security goal describes the secret information “secrecy_of” and the authentication quantity “authentication_o” of the communication entity defined in the protocol shown in Figure6.Figure 6
Description of the safety goals.The OFMC simulation results are shown in Figure6, and the ATSE simulation results are shown in Figure 6. From Figure 7, we can see that the LAAP realizes two-way authentication while resisting man-in-the-middle attacks and replay attacks, which proves the security of the protocol.Figure 7
Verification results of security with AVISPA.
(a)
OFMC backend simulation results(b)
ATSE backend simulation results


## 4.1.1. Formal Security Proof with ROM

The extended RO is described as follows:TestIDDi,NIDi,OIDi is used to query the real identity information of the device, where NIDi and OIDi represent the identity after session key negotiation and the identity before session key negotiation, respectively. CorruptDi,a is used to query the secret information of the device and simulate the attack of the device being stolen.There are two participantsΠ in this work, i.e., server S and the embedded device D. Each participant has multiple instances (i.e., ROs). Let Di and Si represent the i-th instance of them, respectively; DIDi and SIDi represent the identity of Di and Si that are used to negotiate the session key, respectively; NIDi and OIDi indicate the updated ID and the preupdated ID of D, respectively; HDi and HSi, respectively, represent the hash chain status of D and S; SKij represents the negotiated key for the j-th time.If the instanceSi receives all the expected messages according to the predetermined steps, the instance enters the accepting state denoted as AccΠi=1. In this protocol, the parties negotiating the secure session key should meet the following conditions: (1) both S and D enter the receiving state, i.e., AccDi=AccSi=1; (2) D updates the identity, DIDi=NIDi; (3) the identities of S and D are not empty, i.e., DIDi≠null, SIDi≠nullIn the ROM, an attacker can simulate the attack by querying the RO. The included query is defined as follows:Passive attackExecuteDi,Si: the attacker can query the oracle to obtain the messages exchanged between Di and Si, giving the attacker the ability to eavesdrop on the channel.Active attackSendΠ,m: the attacker can interact with any participant by querying the oracle machine, and the oracle machine processes the message. If the message is valid, the oracle machine returns the processing result of message m; if the message is invalid, the oracle machine ignores the message.RevealΠ: the attacker can obtain the session key of any participant by querying the oracle, and this query will only return the held key if the participant actually holds the session key. When an attacker queries the random oracle, the correct session key will be returned only if Π is accepted; otherwise, a random element in the state space will be returned.CorruptDi,a: when a=1, the hash chain value of Di is fed back during the query. If the hash chain value is invalid, the random element in the state space is returned. When a=2, the query information is the registration information Ti of Di. If the registration information Ti is invalid, the random element in the state space is returned.TestIDDi,NIDi,OIDi: the attacker can obtain the real identity of the device by querying the oracle. If the sent message Di is accepted, it will return the real identity of the device; otherwise, it will return a random element in the state space. This oracle is used to test the anonymity of the protocol.TestSKΠ: when the attacker queries the oracle, the RO throws an unbiased coin b, and the result is used to determine whether the query returns the correct result. If b=0, it returns a random element in the state space; if b=1, and the participant holds the session key, return the correct session key; otherwise return it. The oracle tests the security of the negotiated session key, where the query can only be executed once.Semantic security for session keys. In the defined ROM, attackerA can query the session key through RevealΠ or TestSKΠ, and random elements in the state space will be returned during the query process; query through TestIDDi,NIDi,OIDi The real identity of the device. A needs to distinguish between random elements and real information. The goal of A is to guess the real information. At the end of the experiment, the attacker returns a guess bit c∗. If c∗=c, then A wins the game event, which destroys the security of the protocol. Succi denotes that A wins the ith experiment, and P denotes the constructed LAAP protocol. More precisely, the advantage of A overcoming the semantic security of the protocol is Advp=2·PrSucc0−1, if the experiment ends, the probability of obtaining A attack success is negligible, indicating that the protocol is semantically secure.Based on the above definitions, we have the following theorem which proves the security of the proposed protocol.Theorem 3.
LetAdvP denote the advantage of an adversary A to break through the semantic security of the proposed protocol P, and let AdvExSE denote the advantage of A in cracking the ciphertext symmetric encrypted with the server key pair within a probability polynomial, and let AdvEpECDLP denote the advantage of solving the ECDLP problem of Ep in any polynomial time
(2)AdvP≤2qs+qe2+2qt22lh+2AdvEpECDLPt+2AdvExSEt,where Ep and Ex are the elliptic curve group and the symmetric encryption algorithm, respectively, and qs, qe, and qt denote the times that attacker A executes the queries SendΠ,m, ExecuteDi,Si, and TestIDDi,a, respectivelyProof.
LetPrSucci denote the probability that A wins in the i-th experiment. The contribution of the i+1-th experiment to the probability of A winning can be expressed PrSucci−PrSucci+1. The proof process can be described as the following five different experiments.
Experiment 1. This experiment corresponds to a real attack in the ROM. WhenA implements a real attack on the protocol P under the ROM model, we have
(3)AdvP=2·PrSucc0−1.
Experiment 2. This experiment is used to simulate an eavesdropping attack of an adversaryA. We know SK=hAiNID′NID in the protocol, where Ai is calculated by the embedded device through CKi and random number N1, and NID′ is encrypted by the server with the secret key x. Even if intercepting all parameters transmitted during the authentication phase, A still cannot get it any information. Therefore implementing an eavesdropping attack cannot increase the probability of A winning, and we can obtain
(4)PrSucc0=PrSucc1.
Experiment 3. This experiment is used to simulate all possible hash collisions in the authentication phase based on Experiment 2.A tries to find hash collisions, and if the same output is produced for different inputs, the game ends. According to the birthday paradox (the number of collision tests for a hash table of N bit length is not 2N but only N), we have
(5)PrSucc2−PrSucc1≤qs+qe22lh,where qs and qe represent the times that attacker A queries SendΠ,m and ExecuteDi,Si, respectively.
Experiment 4. Based on Experiment 3, attackerA queries the device’s secret information Ti and hash chain value Si by adding TestIDDi,NIDi,OIDi. If A successfully obtains the information, the probability that A wins the experiment is
(6)PrSucc2−PrSucc1≤qt22lh,where qt represents the times that the attacker A queries TestIDDi,a.
Experiment 5. Based on Experiment 4, the experiment adds thatA can tamper with the authentication information and make legitimate participants believe the tampered message, i.e., A can eavesdrop on the message and can make Hash collision. The following two cases will occur: (1) A tampers with message P1, and (2) A tampers with message P3.
Case 1. In this case, after tampering withP1, the adversary needs to solve how to correspond to the verification message P2. For this reason, the adversary needs to solve the ECDLP problem, and guess N1 and CKi, (i.e., 2AdvPECDLPt), so that it can guess CKi. Besides, A still needs to solve a symmetric key problem to generate legal P5, i.e., ADVExSEt. Overall, we have
(7)PrSucc4Case1≤2AdvEpECDLPt+AdvExSEt.
Case 2. In this case,A tampers with P3 to impersonate the server. Assuming that A has obtained the synchronization value Si shared by the device and the server, A still needs to solve the symmetric key decryption problem, i.e., AdvExSEt. Similarly, if A has decrypted the current symmetric key problem, A still needs to solve the ECDLP problem to obtain the legal Ai, i.e., AdvEpECDLPt. Thus, we have
(8)PrSucc4Case2≤AdvEpECDLPt+AdvExSEt.
In summary, the probability that the adversaryA wins in Experiment 5 is
(9)PrSucc4−PrSucc3≤AdvFpECDLPt+AdvExSEt.
All random predictions are simulated in the above four experiments. The results indicate thatA has no advantage in guessing the bit c, and the only way to pass the test is to perform TestSKΠ query guessing, i.e.,
(10)PrSucc4=12.
Using the triangle inequality, we can obtain(11)12AdvP=PrSucc0−PrSucc4.
Based on (3)–(8), we have
(12)PrSucc0−PrSucc4≤qs+qe22lh+qt22lh+AdvPECDLPt+AdvExSEt.
Submitting (12) into (11), we can obtain (2).Remark 4.
This result indicates that the adversaryA has no extra advantage to win the experiment and the proposed scheme is secure.


## 4.1.2. Formal Security Proof with AVISPA Tool

In this part, the AVISPA verification tool is used to verify the security of the LAAP protocol. The experimental environment is Oracle VM VirtualBox, SPAN-Ubuntu10.10-light. The HLPSL language description of the protocol is divided into the following five dimensions.Role attributes:D and S are two agents, Hash and Mutli are two hash functions, Kab is a symmetric key, and Snd and RCV are the communication channels between the client and the outside world. The local variables defined are the same as the protocol description, as shown in Figure 4(a). The modeling of the server is similar to that of the client, as shown in Figure 4(b).Figure 4
Role attributes of the clientD and the serve S.
(a)
Role attribute ofD(b)
Role attribute ofSRole conversion process: the conversion process ofD in LAAP is divided into three stages: register1 means that D starts to register and sends registration information to S; register2 means that D receives the response from S, conducts authentication calculation, and initiates an authentication request; authentication1 indicates that D receives the response from S and completes the final authentication process, as shown in Figure 5(a). Similarly, the conversion process of S is also divided into three stages: register indicates that S requests the registration information of D; authentication1 means that S receives the authentication request of D and performs verification and response; authentication2 means that S receives the response of D and completes the final authentication process, as shown in Figure 5(b).Figure 5
Role change process, session attributes, and environmental attributes.
(a)
Role change process of D(b)
Role change process of S(c)
Session attributes(d)
Environmental attributesSession attributes: the modeling of LAAP session attributes defines the rules that the communicating entities follow. The definition of basic attributes includes the role agentsD and S, hash functions Hash and Multi, symmetric key Qi, and communication channels SND and RCV as shown in Figure 5(c).Environmental attributes: the definition content of LAAP environment includes the communication channel of the communication entity, communication entity (includingd, s, and i), security target constant, and session combination, as shown in Figure 5(d).Safety goals: the security goal describes the secret information “secrecy_of” and the authentication quantity “authentication_o” of the communication entity defined in the protocol shown in Figure6.Figure 6
Description of the safety goals.The OFMC simulation results are shown in Figure6, and the ATSE simulation results are shown in Figure 6. From Figure 7, we can see that the LAAP realizes two-way authentication while resisting man-in-the-middle attacks and replay attacks, which proves the security of the protocol.Figure 7
Verification results of security with AVISPA.
(a)
OFMC backend simulation results(b)
ATSE backend simulation results


## 4.2. Informal Security Analysis

Informal security analysis mainly consists of two parts, i.e., basic function security and common attack defense. Basic functional security includes mutual authentication and device anonymity. Common attacks resistance mainly includes traceable attack defense, asynchronous attack defense, DoS attack defense, replay attack defense, and simulation attack defense.Mutual authentication. In the LAAP protocol, serverS authenticates the legal identity of device D based on the message P1,P2,NID and then restores the identity of the device with NID. This precess is performed through symmetric encryption. If S gets a string of garbled characters after decrypting NID or cannot find matching information in the verification table, S will discard the authentication message. After successfully decrypting NID and obtaining the device’s identity DID, S verifies the authenticity of the device with CKi=hTiSii,P2′=hAi′SiiP1. If P2=P2′, the verification is passed. In the response message P3,P4, P3 contains the new identity of the device, which is encrypted by the hash chain value synchronized by both parties, and P4 contains the authentication information Ai. Notice that only valid S can calculate Ai′. Thus, if the P4′ calculated by the device is the same as the received P4, D can confirm the legal identity of SDevice anonymity. Device anonymity means that attackerA cannot obtain any identifying information about the participants by listening to the messages in the channel. In the LAAP, the method of dynamic pseudonym and synchronous hash chain are used to solve the anonymity of the device. Notice that the identity identification NID is dynamically updated in the second phase of device authentication so that the identity identifications are different at different session stages. Under the Deolv-Yao attack model [31], A is completely unable to distinguish the attribution of different sessions. Therefore, the proposed protocol satisfies the anonymity requirement of the device.Traceable attack defense. Traceable attack means that attackerA can identify the belonging of messages by listening to the information in the channel, so as to carry out specific analysis to undermine the security of the protocol. Recall that the LAAP protocol used the dynamic pseudonym. Thus, after each successful session key negotiation, the device identity is updated. That is, the NIDi sent in the i-th session is completely different from the NIDi+1 sent in the i+1-th session. Therefore, A cannot determine which communication entity the session message belongs to and also cannot track the session information of specific equipment.Asynchronous attack defense. An asynchronous attack intercepts message transmission to make protocol participants lose synchronization. As a result, the protocol cannot be executed correctly, thus destroying the protocol. According to the LAAP, the messages transmitted on the public channel includesP1,P2,NID, P3,P4, and P5. There are two messages related to synchronization information, i.e., the initial authentication message P1,P2,NID and the response message P3,P4 sent by S and D, respectively. For attacker A, intercepting message P1,P2,NID has no effect on the synchronization of the protocol. Thus, we only consider the following two cases.Case 1 (A intercepts the message).
S has updated the device ID as PIDnew=DIDi+1,PIDold=DIDi because S has already processed the message i. At this time, due to the information interception, the identity identifier DIDi of D is the corresponding NIDi. When the timer of D expires, D will regenerate the random number to reauthenticate and send the message P1i,P2i,NIDi to S. We can see that PIDold=DIDi, and S will determine that D is out of synchronization, and the current hash value is directly used for authentication.Case 2 (A intercepts the message P5).
The system status is thatS updated the device ID, and D updated the device ID and hash chain value. After P5 is intercepted, the hash chain value of the protocol participant S is synchronously behind D. When the timer of device D expires, D resends the authentication message P1i+1,P2i+1,NIDi+1, and PIDnew=DIDi+1. the hash chain value will be updated, and Sync will be used in the update process. Therefore, D and S will resume synchronization.DoS attacks defense. DoS attack means that attackerA sends a large amount of invalid authentication information to the server, which consumes the computing resources of the server and makes the server unable to provide services normally. In the protocols in [11, 15], there is a way to find information about related devices by traversing the password check table or the local registry. Thus, their time complexity is On. When there are enough registrations, even if most of the devices are offline, the server will go through all the devices during the authentication process. The proposed LAAP protocol combine the dynamic pseudonym with symmetric encryption, and the time complexity is reduced from On to O1. So, the proposed protocol has a high authentication efficiency and can resist DoS attacks.Replay attacks defense. Replay attack means that the attacker resends the message sent in the history negotiation stage to the server, thus achieving the purpose of spoofing. In LAAP, the messages transmitted by the public channel consistP1,P2,NID,P3,P4, and P5. Let the message sent by the device in the i-th session be P1i,P2i,NIDi, the message sent by the server be P3i,P4i, and the response message from the device be P5i. Thus, there would be the following three cases.Case 1 (A replays the message P1i,P2i,NIDi).
We will analyze it from two subcases. In subcase 1, the attacker launches a replay attack in the middle of thei-th and i+1-th key negotiation at the device side. Note that the device has not performed the i+1-th key negotiation. Because the server will store the ith device identity, the server will find PIDold=DxNIDi in the authentication table and will consider that device is out of asynchrony. So in the next step of message verification, the server will calculate Sync=hAi′ and classify the message as a replay attack and discard the session. In subcase 2, A uses the device history negotiation information P1i−n,P2i−n,NIDi−n, where n∈0,i−1): After receiving P1i−n,P2i−n,NIDi−n, the server uses key symmetric decryption to get the i−n−1-th device identity based on NIDi−n. But the server cannot find the relevant information in the database, and it will discard the session.Case 2 (A replay the message P3i,P4i).
Similarly, we will analyze it from two subcases. Subcase 1 is similar to the above subcase. After receivingP3i,P4i, the device will decrypt P3i to obtain the new device identifier NIDi′. At this time, the hash chain value at the device has been updated, and P4i′ computed by the device is different from the received P4. So, the device will terminate the session. For subcase 2, after receiving the history information P3i−n,P4i−n (where n∈0,i−1), the device will decrypt P3i−n to get the identity NIDi−n+1. However, because the hash chain value has been updated several times, NIDi−n+1′ obtained by decrypting P4i−n′ is different from P4i−n. Thus, the device will terminate the session.Case 3 (A replay the historical message P5i).
The server will use the new authentication information and message to calculate as follows:(13)SK=hAi_new′NIDnew′NIDnew,P5_new′=hSKnewSKnew.We can find thatP5_new′ is different from P5i. Thus, the session key negotiation cannot be successful, and the server will discard the session.Based on the analysis of the above three cases, we proof that the proposed protocol can resist the replay attacks.Simulation attack defense. An emulation attack means that the attacker tampers authentication information to establish session keys on the simulated device or server. An attackerA can tamper with or send historical authentication messages to spoof the device or the server based on the intercepted authentication messages.For messagesP1,P2,NID, A has no access to the registration information Ti and the synchronization hash value of the device, so it cannot obtain the legitimate P2 to spoof S. If A replays the historical messages, see the above analysis for details. For messages P3,P4, A cannot know symmetric encryption key x of S and the authentication message Ai′ generated in this session, so it cannot compute the legitimate P3 and P4. If A replays the historical message, the session is terminated due to authentication failure. For message P5, A cannot know the authentication message Ai′ of this session, so that it cannot compute P5. If A replays the history message, the authentication will fail, and S terminates the session. In summary, the proposed protocol can resist the simulation attacks.We provide Table2 to show the comparison of security performance between LAAP and the benchmarks. The dimension of comparison is based on the basic functional security and common attack resistance described in the above. In Table 2, where “Yes” (resp. “No”) indicate that the protocol can (cannot) support the security feature, and “—” indicates that the protocol does not involve this security feature. From Table 2, we can see that the proposed LAAP protocol can resist more security attacks.Table 2
Comparison of security performance.
IndexS1S2S3S4S5S6S7BenchCwsNoNoNoNoYesNo—WangYesNoYesNoYesNo—PandaYesYesYesYesYesNo—RostampourYesYesYesYesNoYes—BhuaryaYesYesYesYesYesNo—LAAPYesYesYesYesYesYesYesS1-S7 are the index of the mutual authentication, device anonymity, traceable attack defense, asynchronous attack defense, DoS attacks defense, replay attacks defense, and simulation attack defense, respectively.


## 5. Performance Evaluation

In this section, we provide the performance comparisons between the prosed LAAP protocol with several related protocols [9–11, 15] in terms of computational overhead, storage overhead, and communication overhead. For a fair comparison, all experiments use the http://golang.org/x/crypto/bn256 curve and the hash function SHA-256.


### 5.1. Computational Cost Analysis

We first provide the comparison of a computational overhead between the proposed protocol and the benchmarks. The computational cost is divided into the time-consuming of the device in the registration phase and the authentication phase. The calculation overhead is shown in Table3. From Table 3, we can see that in the registration stage, the proposed protocol increases the computational overhead of the device but reduces the overhead of the server. We also can observe that in the authentication stage, we reduce the computational overhead of both the device and server. Finally, the results of total overhead indicate that the proposed scheme outperforms the benchmarks.Table 3
The comparison of calculation overhead (ms).
Regist.Authen.Total[9]Device071.0163206.4185Server53.417481.9848[10]Device066.0148183.1098Server54.887262.2078[11]Device9.824193.9545318.3577Server52.4631162.116[15]Device0.575194.8175328.901Server12.0247221.4837LAAPDevice45.170546.3724149.3163Server12.99844.7754In order to show the total computation cost under different numbers of devices, we plot Figure8. We can observe that compared with the benchmarks, the proposed protocol can bring a lower computation cost. Furthermore, as the number of devices increases, the performance improvement of our protocol becomes more obvious. Therefore, the proposed protocol is more suitable for deployment in the IoT with a large number of devices.Figure 8
Total computation cost vs. various number of devices.


### 5.2. Storage Cost Analysis

Here, we provide the comparison of the store overhead between the proposed protocol and the benchmarks. The store cost consists the space-consuming of the device in the registration phase and the authentication phase. In the analysis process, SHA-256 and bn256 are used as the hash function and elliptic curve, respectively.According to Figure2, the storage information at the device includes NIDi, Ti, and Si. So the storage space required at the device side is 256+256+256=768 bits in the registration phase. As Figure 3 shown, the storage space required by the server is 256+256+256+256+256=1280 bits in the authentication phase. The storage overhead of the benchmarks is calculated in the same way, and the detailed data is shown in Table 4. To show the comparison results more visually, we provide Figure 9. We can observe that the storage space required by the LAAP protocol at the device is consistent with the minimum storage required by the benchmarks, and the store overhead at the server only be higher than the protocol in [11]. Thus, our protocol requires higher storage overhead than the protocol in [11] but lower than other protocols in [9, 10, 15].Table 4
The comparison of store overhead (bits).
RegistrationAuthenticationTotal[9]102412802304[10]76812802048[11]7687681536[15]153617933329LAAP76812802048Figure 9
Storage cost comparison.


### 5.3. Communication Cost Analysis

Finally, we provide the comparison of the communication cost between the proposed protocol and the benchmarks. Similarly, the communication cost consists the consumption of the device in the registration phase and the authentication phase.According to Figure2, the information transmitted by the device includes Z1, PPIDi, Z3, and P4. So the communication cost in the registration phase is 256+512+256+256=1280 bits. As Figure 3 shown for the proposed protocol, the communication overhead at the server is 512+256+256+256+256+256=1792 bits in the authentication phase. The communication overhead of the benchmarks is calculated in the same way and the detailed data is shown in Table 5..Table 5
The comparison of communication overhead (bits).
RegistrationAuthenticationTotal[9]102425603584[10]76823043072[11]76830723840[15]128023043584LAAP128017923072We further provide Figure10 to show the detailed comparison. We can see from Figure 10 that the communication overhead of the proposed protocol in the registration phase is slightly higher than the benchmarks. That is due to the fact that the proposed protocol takes necessary encryption measures to ensure public channel registration. However, the proposed protocol takes the lowest communication overhead. Considering that in practical applications, the number of registration stages is much less than the number of authentication stages, it is acceptable to increase the overhead of registration stage slightly. We can also find that the proposed protocol has the lowest total communication overhead and an average of 12.73% reduction in terms of communication overhead compared to other protocols.Figure 10
Communication cost comparison.


### 5.4. Performance Analysis under Different Number of Devices

To verify the performance of the proposed protocol under a large number of devices, the stress testing tool GO-WRK and custom scripts are used in this subsection to analyze the performance of the device registration module, server registration module, and identity authentication module of the system.We first analyze the average response time for different numbers of the devices in the registration phase in Table6. We can see that when the number of registered devices is less than 1400, the server has a relatively fast response rate, and the average response time is 48.57 ms. When the number of registered devices is greater than 1400, the response time increases proportionally as the number of devices increases. It indicates that when the number of registrations is higher than 1400, the system performance is saturated and all resources are fully utilized.Table 6
Average response time of devices in the registration phase (ms).
Num.Ave-timeSuc. rateNum.Ave-timeSuc. rate20048.31100%180093.23100%60047.32100%2000122.76100%100048.03100%2200157.72100%140050.61100%2400189.31100%160060.87100%2600225.12100%Num.: number of devices; Ave. time: average response time; Suc. rate: success rate.Then, we provide Table7 to show the average cost under the different number of devices in the certificate phase. As shown in Table 7, under the LAAP protocol, the average time consumption of the devices is 58.15 ms, and as the number of concurrent devices increases, the device time consumption is basically stable. When the server does not reach saturation, the server takes an average of 64.1 ms. After the server reaches saturation, the response time of the server increases with the number of concurrent authentication devices. The saturation threshold of the server is 1200 devices. In the case of a single server, the server can quickly complete the authentication and key negotiation of 1200 devices.Table 7
Average cost in the certification phase.
Num.D-Cost (ms)S-Cost (ms)Aut-efficiency20058.1163.21100%40056.9865.79100%60056.4364.33100%80057.2163.31100%100056.4562.75100%120058.9765.21100%Num.: number of devices; D-Cost and S-Cost: average cost at device and serve, respectively.


## 5.1. Computational Cost Analysis

We first provide the comparison of a computational overhead between the proposed protocol and the benchmarks. The computational cost is divided into the time-consuming of the device in the registration phase and the authentication phase. The calculation overhead is shown in Table3. From Table 3, we can see that in the registration stage, the proposed protocol increases the computational overhead of the device but reduces the overhead of the server. We also can observe that in the authentication stage, we reduce the computational overhead of both the device and server. Finally, the results of total overhead indicate that the proposed scheme outperforms the benchmarks.Table 3
The comparison of calculation overhead (ms).
Regist.Authen.Total[9]Device071.0163206.4185Server53.417481.9848[10]Device066.0148183.1098Server54.887262.2078[11]Device9.824193.9545318.3577Server52.4631162.116[15]Device0.575194.8175328.901Server12.0247221.4837LAAPDevice45.170546.3724149.3163Server12.99844.7754In order to show the total computation cost under different numbers of devices, we plot Figure8. We can observe that compared with the benchmarks, the proposed protocol can bring a lower computation cost. Furthermore, as the number of devices increases, the performance improvement of our protocol becomes more obvious. Therefore, the proposed protocol is more suitable for deployment in the IoT with a large number of devices.Figure 8
Total computation cost vs. various number of devices.


## 5.2. Storage Cost Analysis

Here, we provide the comparison of the store overhead between the proposed protocol and the benchmarks. The store cost consists the space-consuming of the device in the registration phase and the authentication phase. In the analysis process, SHA-256 and bn256 are used as the hash function and elliptic curve, respectively.According to Figure2, the storage information at the device includes NIDi, Ti, and Si. So the storage space required at the device side is 256+256+256=768 bits in the registration phase. As Figure 3 shown, the storage space required by the server is 256+256+256+256+256=1280 bits in the authentication phase. The storage overhead of the benchmarks is calculated in the same way, and the detailed data is shown in Table 4. To show the comparison results more visually, we provide Figure 9. We can observe that the storage space required by the LAAP protocol at the device is consistent with the minimum storage required by the benchmarks, and the store overhead at the server only be higher than the protocol in [11]. Thus, our protocol requires higher storage overhead than the protocol in [11] but lower than other protocols in [9, 10, 15].Table 4
The comparison of store overhead (bits).
RegistrationAuthenticationTotal[9]102412802304[10]76812802048[11]7687681536[15]153617933329LAAP76812802048Figure 9
Storage cost comparison.


## 5.3. Communication Cost Analysis

Finally, we provide the comparison of the communication cost between the proposed protocol and the benchmarks. Similarly, the communication cost consists the consumption of the device in the registration phase and the authentication phase.According to Figure2, the information transmitted by the device includes Z1, PPIDi, Z3, and P4. So the communication cost in the registration phase is 256+512+256+256=1280 bits. As Figure 3 shown for the proposed protocol, the communication overhead at the server is 512+256+256+256+256+256=1792 bits in the authentication phase. The communication overhead of the benchmarks is calculated in the same way and the detailed data is shown in Table 5..Table 5
The comparison of communication overhead (bits).
RegistrationAuthenticationTotal[9]102425603584[10]76823043072[11]76830723840[15]128023043584LAAP128017923072We further provide Figure10 to show the detailed comparison. We can see from Figure 10 that the communication overhead of the proposed protocol in the registration phase is slightly higher than the benchmarks. That is due to the fact that the proposed protocol takes necessary encryption measures to ensure public channel registration. However, the proposed protocol takes the lowest communication overhead. Considering that in practical applications, the number of registration stages is much less than the number of authentication stages, it is acceptable to increase the overhead of registration stage slightly. We can also find that the proposed protocol has the lowest total communication overhead and an average of 12.73% reduction in terms of communication overhead compared to other protocols.Figure 10
Communication cost comparison.


## 5.4. Performance Analysis under Different Number of Devices

To verify the performance of the proposed protocol under a large number of devices, the stress testing tool GO-WRK and custom scripts are used in this subsection to analyze the performance of the device registration module, server registration module, and identity authentication module of the system.We first analyze the average response time for different numbers of the devices in the registration phase in Table6. We can see that when the number of registered devices is less than 1400, the server has a relatively fast response rate, and the average response time is 48.57 ms. When the number of registered devices is greater than 1400, the response time increases proportionally as the number of devices increases. It indicates that when the number of registrations is higher than 1400, the system performance is saturated and all resources are fully utilized.Table 6
Average response time of devices in the registration phase (ms).
Num.Ave-timeSuc. rateNum.Ave-timeSuc. rate20048.31100%180093.23100%60047.32100%2000122.76100%100048.03100%2200157.72100%140050.61100%2400189.31100%160060.87100%2600225.12100%Num.: number of devices; Ave. time: average response time; Suc. rate: success rate.Then, we provide Table7 to show the average cost under the different number of devices in the certificate phase. As shown in Table 7, under the LAAP protocol, the average time consumption of the devices is 58.15 ms, and as the number of concurrent devices increases, the device time consumption is basically stable. When the server does not reach saturation, the server takes an average of 64.1 ms. After the server reaches saturation, the response time of the server increases with the number of concurrent authentication devices. The saturation threshold of the server is 1200 devices. In the case of a single server, the server can quickly complete the authentication and key negotiation of 1200 devices.Table 7
Average cost in the certification phase.
Num.D-Cost (ms)S-Cost (ms)Aut-efficiency20058.1163.21100%40056.9865.79100%60056.4364.33100%80057.2163.31100%100056.4562.75100%120058.9765.21100%Num.: number of devices; D-Cost and S-Cost: average cost at device and serve, respectively.


## 6. Conclusion

In this work, we proposed a lightweight anonymous authentication protocol named LAAP against asynchronous attacks to realize the anonymous authentication between device and server in the IoT. Through informal security analysis and formal security analysis, we found that the proposed protocol has the following advantages: (1) it can solve the problem that the device identification is fixed and easy to be tracked by dynamically updating the identification; (2) the hashing chain value of communication devices can be adaptively synchronized to resist asynchronization attack; (3) the time complexity of finding the registration information of the device through the anonymous identity of the device isO1. Besides, extensive results were provided to indicate that the total overhead is lower than the benchmarks.Note that this work only considers identity authentication within a single network domain. Therefore, the lightweight anonymous authentication of the IoT across network domains will be the future research direction. In addition, using the intelligent algorithms [32] to optimize our methods and solve the authentication of large-scale heterogeneous devices are also the future research.



---

*Source: 8768928-2022-09-22.xml*