# ULMAP: Ultralightweight NFC Mutual Authentication Protocol with Pseudonyms in the Tag for IoT in 5G

Authors: Kai Fan; Panfei Song; Yintang Yang
Journal: Mobile Information Systems
 (2017)

---

## Abstract

As one of the core techniques in 5G, the Internet of Things (IoT) is increasingly attracting people’s attention. Meanwhile, as an important part of IoT, the Near Field Communication (NFC) is widely used on mobile devices and makes it possible to take advantage of NFC system to complete mobile payment and merchandise information reading. But with the development of NFC, its problems are increasingly exposed, especially the security and privacy of authentication. Many NFC authentication protocols have been proposed for that, some of them only improve the function and performance without considering the security and privacy, and most of the protocols are heavyweight. In order to overcome these problems, this paper proposes an ultralightweight mutual authentication protocol, named ULMAP. ULMAP only uses Bit and XOR operations to complete the mutual authentication and prevent the denial of service (DoS) attack. In addition, it uses subkey and subindex number into its key update process to achieve the forward security. The most important thing is that the computation and storage overhead of ULMAP are few. Compared with some traditional schemes, our scheme is lightweight, economical, practical, and easy to protect against synchronization attack.


---

## Body

## 1. Introduction

IoT [1] is a large network that consists of various information sensing devices and the Internet. As a new technology, the NFC [2, 3] is one of the core technologies of IoT and is listed as one of the most promising technologies.NFC is a short-range, high-frequency, noncontact automatic identification wireless communication technology using the 13.56 MHz frequency band at a distance of less than 10 cm. It is a development and breakthrough of the RFID [4–6] technology. NFC now has been widely used in electronic ticket, product security, and other fields. But the security issues, especially the authentication problem between the reader and the tag, have become an important factor restricting its development. The problem of authentication is to confirm the validity of the tag and the reader. Since NFC communication is completely exposed to the wireless environment, it faces a lot of malicious attacks such as clone attack [7, 8], man-in-the-middle attack, and packet losses attack. Once the authentication protocol is under the above attack, the authentication will be failed. Meanwhile, because the NFC system is limited by many factors, such as computing power, storage space, and power supply, it is a challenging task to design a secure and efficient NFC authentication protocol.So far, although a lot of security authentication schemes for NFC are presented, researchers at home and abroad do not put forward a universal applicability scheme. For example, Yun-Seok et al. [3] proposed a scheme that uses the asymmetric encryption and hash function to try to eliminate the security and privacy thread. Although the solution can solve the problem of mutual authentication and prevent replay attack and the man-in-the-middle attack, it lacks some necessary security attributes, such as the message authentication. In 2013, Eun et al. [9] presented a new conditional privacy preserving security protocol to protect the user’s privacy. In 2015, Kannadhasan et al. [10] proposed the similar approach as presented in CPPNFC. In the same year, He et al. [11] proposed a pseudonym-based NFC protocol, but it cannot solve the forward security. In order to better promote the NFC technology, a scheme is needed to be proposed to solve the security and privacy thread.Therefore, in this paper, we propose an ultralightweight mutual authentication protocol (ULMAP). Compared with the old NFC scheme, this protocol not only solves the security and privacy problem but also reduces the computation and storage cost.Our Contributions. In this paper, we propose an ultralightweight mutual authentication protocol (ULMAP) for NFC using less memory storage and computational power for low-cost NFC tags. Our scheme has the following features:(1)
Ultralightweight: the scheme is designed only with simple shift and XOR operations, not hash or other encryption operations.(2)
Secure and efficient: the scheme we proposed could meet requirements of forward security, mutual authentication, synchronization, and non-denial of service by subkey and pseudonym.Paper Organization. The remainder of the paper is organized as follows: In Section 2, we will present the detailed protocol of our new NFC mutual authentication protocol (ULMAP). In Section 3, the security proof with BAN logic of the proposed protocol will be provided. Section 4 provides the security and performance analysis of our protocol. Finally, our conclusion is shown in Section 5.


## 2. NFC Authentication Protocol for Mobile Device

In this section, we will propose ULMAP and basic ideas are as follows: the scheme only with a simple shift and XOR operations, greatly reducing the cost of operations. And it uses the concept of pseudonym, thus improving the system of security. And the scheme uses the concept of subkeys, preventing the man-in-the-middle attack as compared to the related existing authentication protocols.


### 2.1. Initialization

The explanations of symbols are shown in Abbreviation.M
i
x
B
i
t
s
(
X
,
Y
) [12] is defined as follows:Z=MixBits(X,Y)⋮Z=X;fori=0;i<32;i++Z=Z≫1+Z+Z+Y;In this scheme, the messageIDS,ID,K1,K2 is stored in each tag. Meanwhile, ID,IDSold,Kold1,Kold2,IDSnew,Knew1,Knew2 is stored in the server corresponding to each tag.


### 2.2. The Authentication Process

The authentication process of ULMAP is shown in Figure1. The protocol involves three entities: tag, reader, and database. The channel between the reader and the database is assumed to be secure, but that between the reader and the tag faces all the possible potential attacks [13–15]. Each tag has a unique static identification (ID) and preshares a pseudonym (IDS) and two keys K1,K2 with the database.Figure 1
Authentication process of ULMAP.Each database actually has two entries ofID,IDSold,Kold1,Kold2,IDSnew,Knew1,Knew2: one is for the old values and the other is for the potential next values. The reader first sends “Query” and TR message to the tag. The tag will respond with its IDS after it verifies that the timestamp TR is larger than Tt. Then, the reader will use the tag’s response IDS to find a matched entry in the database and goes to the mutual authentication stage if a matched entry is found no matter what IDS=IDSold or IDS=IDSnew. In the mutual authentication phase, the reader and the tag authenticate each other, and they, respectively, update their local pseudonym and the keys after successful authentication, which are shown in Figure 1.There are four stages in the scheme that we proposed, such as initialization, tag identification, mutual authentication, and index-pseudonym and key updating. Then, we will in detail introduce the four stages as follows.Initialization. The database selects a pseudorandom generator PRNG [16] g:0,1k→0,12k to generate pseudorandom number. The database generates the key K=K1∣K2, which is initialized to K1=RotRotni,2+ID+ni,3,ni,2+ID,ni,1+ni,3 and K2=RotRotni,1+ID+ni,3,ni,1+ID,ni,2⊕ni,3, and places it in a valid tag and the legitimate reader. ni,j is the jth random number of the ith tag in the initialization phase, j=1,2,3. The database, reader, and tag will store the IDS and K=K1∣K2 corresponding to the tag.Tag Identification. The reader generates the random timestamp TR and the random number n2 and sends authentication queries n2, Query, and TR to the tag. Then, the tag judges whether TR>Tt; if TR is not larger than Tt, the authentication is failed. Otherwise, the mutual authentication phase will begin.Mutual Authentication. After identification phase, the tag will generate a random number n2, calculate A, B, and C as shown in Figure 1, and send IDS, A, B, and C to the reader. Using the IDS, the reader tries to find an identical entry in the database. If this search succeeds, the reader can get the nonce from submessages A and B. Then, the reader will compute n3′ and K1∗¯/K2∗¯ and build a local version of submessage C′ as shown in Figure 1. It will be compared with the received value. If it is verified, the tag is authenticated. Finally, the reader sends message D=(K¯⊕ID)⊕((K2+K1)∪K2∗¯) to the tag. When the message D is received by the tag, it will be compared with a computed local version D′=(K¯1⊕ID)⊕K2+K1∪K¯2. If comparison is successful, the reader is authenticated. Otherwise, the authentication protocol is failed.Index-Pseudonym and Key Updating. After successfully completing the mutual authentication phase between the tag and the reader, they locally update IDS and key as indicated in Figure 1.


## 2.1. Initialization

The explanations of symbols are shown in Abbreviation.M
i
x
B
i
t
s
(
X
,
Y
) [12] is defined as follows:Z=MixBits(X,Y)⋮Z=X;fori=0;i<32;i++Z=Z≫1+Z+Z+Y;In this scheme, the messageIDS,ID,K1,K2 is stored in each tag. Meanwhile, ID,IDSold,Kold1,Kold2,IDSnew,Knew1,Knew2 is stored in the server corresponding to each tag.


## 2.2. The Authentication Process

The authentication process of ULMAP is shown in Figure1. The protocol involves three entities: tag, reader, and database. The channel between the reader and the database is assumed to be secure, but that between the reader and the tag faces all the possible potential attacks [13–15]. Each tag has a unique static identification (ID) and preshares a pseudonym (IDS) and two keys K1,K2 with the database.Figure 1
Authentication process of ULMAP.Each database actually has two entries ofID,IDSold,Kold1,Kold2,IDSnew,Knew1,Knew2: one is for the old values and the other is for the potential next values. The reader first sends “Query” and TR message to the tag. The tag will respond with its IDS after it verifies that the timestamp TR is larger than Tt. Then, the reader will use the tag’s response IDS to find a matched entry in the database and goes to the mutual authentication stage if a matched entry is found no matter what IDS=IDSold or IDS=IDSnew. In the mutual authentication phase, the reader and the tag authenticate each other, and they, respectively, update their local pseudonym and the keys after successful authentication, which are shown in Figure 1.There are four stages in the scheme that we proposed, such as initialization, tag identification, mutual authentication, and index-pseudonym and key updating. Then, we will in detail introduce the four stages as follows.Initialization. The database selects a pseudorandom generator PRNG [16] g:0,1k→0,12k to generate pseudorandom number. The database generates the key K=K1∣K2, which is initialized to K1=RotRotni,2+ID+ni,3,ni,2+ID,ni,1+ni,3 and K2=RotRotni,1+ID+ni,3,ni,1+ID,ni,2⊕ni,3, and places it in a valid tag and the legitimate reader. ni,j is the jth random number of the ith tag in the initialization phase, j=1,2,3. The database, reader, and tag will store the IDS and K=K1∣K2 corresponding to the tag.Tag Identification. The reader generates the random timestamp TR and the random number n2 and sends authentication queries n2, Query, and TR to the tag. Then, the tag judges whether TR>Tt; if TR is not larger than Tt, the authentication is failed. Otherwise, the mutual authentication phase will begin.Mutual Authentication. After identification phase, the tag will generate a random number n2, calculate A, B, and C as shown in Figure 1, and send IDS, A, B, and C to the reader. Using the IDS, the reader tries to find an identical entry in the database. If this search succeeds, the reader can get the nonce from submessages A and B. Then, the reader will compute n3′ and K1∗¯/K2∗¯ and build a local version of submessage C′ as shown in Figure 1. It will be compared with the received value. If it is verified, the tag is authenticated. Finally, the reader sends message D=(K¯⊕ID)⊕((K2+K1)∪K2∗¯) to the tag. When the message D is received by the tag, it will be compared with a computed local version D′=(K¯1⊕ID)⊕K2+K1∪K¯2. If comparison is successful, the reader is authenticated. Otherwise, the authentication protocol is failed.Index-Pseudonym and Key Updating. After successfully completing the mutual authentication phase between the tag and the reader, they locally update IDS and key as indicated in Figure 1.


## 3. Security Proof with BAN Logic

The security assurance of the proposed protocol is the secure mutual authentication, which means the following security aims should be achieved.Security Aim 1. The database needs to make sure the received message IDS∥A∥B∥C is exactly the one sent by the tag. This means that we need to achieve Database≡Tag~IDS,A,B,C and Database≡Tag≡IDS,A,B,C.Security Aim 2. The tag needs to make sure the received message D is exactly the one sent by the database, which means the following formulas need to be achieved: Tag≡Database~D and Tag≡Database≡D.


### 3.1. Security Assumption

According to the given protocol and the assumption that the server and the reader are connected securely, the following conditions can be achieved:AS1:Database≡Database⇄ni,jTagi.AS2:Tagi≡Database⇄ni,jTagi.AS3:Reader⟹(n1).AS4:Reader≡#(n1).AS5:Database≡#(n1).AS6:Tagi⟹(n2).AS7:Tagi≡#(n2).


### 3.2. Security Analysis

According to the proposed protocol (ULMAP)K1=RotRotni,2+ID+ni,3,ni,2+ID,ni,1+ni,3 and K2=RotRotni,1+ID+ni,3,ni,1+ID,ni,2⊕ni,3, together with the assumptions AS1 and AS2, we can deduce Tagi≡Database⇄Ki,jTagi and Database≡Database⇄Ki,jTagi, because, in this scheme, the database will receive the message (IDS,A,B,C) forwarded from the reader, where C=K1⊕K2¯+K2⊕K1¯. As we have achieved Ki,j as secret between the database and the tag, we can take Ki,j as the secret key to protect messages. So we can simply write the received message of database as IDS,A,B,CKi,j, and we have Database⊲IDS,A,B,CKi,j. For the reason of “message-meaning rule” of BAN P≡Q∥YP,P⊲XY/P≡(Q~X), we can deduce Database≡Tagi~(IDS,A,B,C).From the assumptionAS5:Server≡#n1 and the BAN rule of P≡#(X)/P≡#(X,Y), we know Database≡#IDS,A,B,C. Because we have achieved Database≡Tagi~#IDS,A,B,C, together with the “nonce-verification” rule P≡(#(X)),P≡(Q~X)/P≡(Q≡X), we will achieve Database≡Tagi≡IDS,A,B,C, and the first security aim of the given protocol is achieved.For the same reason, we can also deduceTagi≡Database~D and Tagi≡Database≡D, and the second security aim is also achieved, and the security of mutual authentication of the proposed protocol has been proved.


## 3.1. Security Assumption

According to the given protocol and the assumption that the server and the reader are connected securely, the following conditions can be achieved:AS1:Database≡Database⇄ni,jTagi.AS2:Tagi≡Database⇄ni,jTagi.AS3:Reader⟹(n1).AS4:Reader≡#(n1).AS5:Database≡#(n1).AS6:Tagi⟹(n2).AS7:Tagi≡#(n2).


## 3.2. Security Analysis

According to the proposed protocol (ULMAP)K1=RotRotni,2+ID+ni,3,ni,2+ID,ni,1+ni,3 and K2=RotRotni,1+ID+ni,3,ni,1+ID,ni,2⊕ni,3, together with the assumptions AS1 and AS2, we can deduce Tagi≡Database⇄Ki,jTagi and Database≡Database⇄Ki,jTagi, because, in this scheme, the database will receive the message (IDS,A,B,C) forwarded from the reader, where C=K1⊕K2¯+K2⊕K1¯. As we have achieved Ki,j as secret between the database and the tag, we can take Ki,j as the secret key to protect messages. So we can simply write the received message of database as IDS,A,B,CKi,j, and we have Database⊲IDS,A,B,CKi,j. For the reason of “message-meaning rule” of BAN P≡Q∥YP,P⊲XY/P≡(Q~X), we can deduce Database≡Tagi~(IDS,A,B,C).From the assumptionAS5:Server≡#n1 and the BAN rule of P≡#(X)/P≡#(X,Y), we know Database≡#IDS,A,B,C. Because we have achieved Database≡Tagi~#IDS,A,B,C, together with the “nonce-verification” rule P≡(#(X)),P≡(Q~X)/P≡(Q≡X), we will achieve Database≡Tagi≡IDS,A,B,C, and the first security aim of the given protocol is achieved.For the same reason, we can also deduceTagi≡Database~D and Tagi≡Database≡D, and the second security aim is also achieved, and the security of mutual authentication of the proposed protocol has been proved.


## 4. Evaluation

In this section, we will analyze the proposed protocol (ULMAP) from the security and performance point of view.


### 4.1. Security Analysis

It is obvious, from the protocol specification, that not only can the tag and the reader successfully authenticate each other, but also ULMAP is able to resist the common NFC attacks effectively. In particular, it makes the scheme have the anti-DoS attack capability through using the timestamp. We now analyze our proposed scheme from the point of view of security as follows.


#### 4.1.1. Mutual Authentication

The tag and the reader can authenticate each other by messagesC and D, because only the genuine tag has the subkeys K1 and K2 which generate the consistent message C with random numbers n1, n2. Similarly, only the genuine reader keeps the ID that is used to generate the response message D. In this way, the reader and the tag can achieve mutual authentication.


#### 4.1.2. Tag Anonymity

The tag uses the pseudonym in the whole authentication process. The pseudonym of each tag will be updated after every successful authentication by the random numbersn1, n2. So the pseudonym from the same tag looks different at each session authentication and the attackers cannot get the real identity of the tag. Moreover, even if the attackers intercept authentication pseudonym IDS, they cannot analyze the practical information from it.


#### 4.1.3. Resistance to Tracking

The data stored in the database and the tag will be updated after the successful authentication process. So the message and the response message are different at each session authentication, making it almost impossible for the attackers to track the tag. In addition, the tag uses the pseudonym which improves the difficulty of tracking.


#### 4.1.4. Data Confidentiality [17]

The calculation of each value ofA,B,C, and D involves at least two secret values, including the subkey and random number. So, it is very hard to get the tag ID except for the tag itself that has K1,K2 and n1, n2.


#### 4.1.5. Forward Security

After each successful session, the key andIDS value will be updated in the tag and the database. So even if the attacker achieves some session information, he cannot use it to trace back to previous communications. In addition, ULMAP makes the subkey and random number involved in the entire update process, which makes the entire update process have stronger stochastic properties. So ULMAP is forward security.


#### 4.1.6. Nonreplaying

Because the value ofIDS will be updated after the successful authentication process, the response message IDS∥A∥B∥C from the same tag is different in each session authentication process. Moreover, the timestamp TR is constantly changing over time. Therefore, the attacker cannot priorly disguise information to achieve legality certification.


#### 4.1.7. Non-Denial of Service (Non-DoS) [18]

When the reader starts a new session, the tag will judge whetherTR > Tt. If not, the authentication is failed. Otherwise, the authentication process will continue. Compared with all most schemes responding to the query, ULMAP can reduce the number of denial of service attacks to some extent and prevent unauthorized readers from continuing to send queries which consume lots of resources of the tag. Therefore, this scheme can resist denial of service attacks in some cases.The comparison between LMAP [19], SASI [20], and ULMAP in security is shown in Table 1. “√” means satisfaction, “×” means to dissatisfy, and “#” means satisfaction to a certain extend.Table 1
The security and functionality comparison.
Scheme
Mutual authentication and forward security
Confidentiality and anonymity
Resistance to tracking
Nonreplaying
Resistance to desynchronization attack
Non-DoS
LMAP
×
×
×
×
×
×
SASI
√
√
√
√
×
×
ULMAP
√
√
√
√
√
#It is very obvious, in Table1, that neither of SASI and LMAP can resist desynchronization and DoS attacks. However, in addition to the forward security, data confidentiality, nonreplaying, and so forth, the proposed protocol ULMAP can prevent synchronicity attacks effectively and prevent DoS attacks to some extent. In summary, ULMAP improves the security.


#### 4.1.8. Synchronization

In a normal session, if the tracker heads off the last message that the database sends to the tag, the database cannot be successfully verified. Once this case happens, the tag cannot be updated, but the database has been updated successfully. So the tag and the database will lose the synchronization. However, in the ULMAP protocol, theIDS, K1, K2, used in the last session is stored in ID,IDSold,Kold1,Kold2,IDSnew,Knew1,Knew2 in the database, so that this tag is still able to finish the authentication and get the synchronization again successfully.


### 4.2. Performance and Complexity Analysis

We will compare ULMAP with SASI and LMAP in performance and complexity. In order to compare easily, assume there arem tags in the system and the length of data is L.


#### 4.2.1. The Cost of Storage

To achieve the authentication, in SASI protocol, the tag stores the message(ID,(IDSnew,K1new,K2new)(IDSold,K1old,K2old)) and (ID,IDS,K1,K2) is stored in the database, so the cost of storage in the tag and database is 7L and 4mL, respectively. As it is shown in Table 2, in LMAP, the tag storage space needs 6L and the corresponding database storage space requires 6mL. But in our protocol, the cost of storage space in the tag is 5L and the cost of storage space in the database is 7mL.Table 2
The storage overhead comparison.
Scheme
Database
Reader
Tag
LMAP
6
m
l
0
6
L
SASI
4
m
l
0
7
L
ULMAP
7
m
l
0
5
LUsually, the database has more resources than the tag, so the resource of tag is more valuable. Comparing with other protocols, the ULMAP needs smaller storage space in the tag that will greatly reduce the cost of the tag and increase a little cost of storage space in the database. Therefore, the proposed protocol can greatly reduce input cost. The specific storage overhead is shown in Table2.


#### 4.2.2. The Cost of Communication

The cost of communication consists of the number of interactions and the length of the communication data. From Table3, we can know that the interaction times of both SASI and LMAP are 4. Although the transmitted data is increased a little, our protocol is just transmitted three times between the reader and the tag, which are four times in other protocols. Therefore, ULMAP has a relatively low communication overhead.Table 3
The cost of communication comparison.
Scheme
The number of interactions
Total cost of communication
LMAP
4
5
L
SASI
4
5
L
ULMAP
3
7
LComparing with other protocols, the ULMAP uses the timestamp for the first time. This will make the ULMAP resist the attack of DoS to a certain extent. Moreover, the subkey and random numbers are used widely in the database and the tag in the authentication update phase. This can make the whole protocol have stronger random feature which will greatly improve the ability of resisting desynchronization and the forward security of ULMAP.


#### 4.2.3. The Cost of Computation Time

In order to better compare the computation performance of different protocols in Table4, + represents AND operation, ⊕ represents the XOR operation, Rot is the displacement Rot(x,y) operation, Rot2 is two displacement Rot(x,y) operations, and T represents the pseudorandom number or timestamp.Table 4
Computation cost comparison.
Scheme
LMAP
SASI
ULMAP
Cost
⊕
,
+
,
∧
,
∨
⊕
,
+
,
∧
,
∨
,
R
o
t
⊕
,
+
,
∧
,
∨
R
o
t
2
,
M
i
x
B
i
t
sFrom Table4, it is shown that the tag in ULMAP needs one random number generation. In addition, ULMAP also needs more computation operation (like Rot, MixBits) in the tag compared with SASI and Gossamer. Although this will increase the cost of computation, the computations also become more secure and effective with it.By comparing our protocol with other schemes, it shows that our proposed protocol not only can provide mutual authentication function but also has the advantage of higher level of security and performance.


## 4.1. Security Analysis

It is obvious, from the protocol specification, that not only can the tag and the reader successfully authenticate each other, but also ULMAP is able to resist the common NFC attacks effectively. In particular, it makes the scheme have the anti-DoS attack capability through using the timestamp. We now analyze our proposed scheme from the point of view of security as follows.


### 4.1.1. Mutual Authentication

The tag and the reader can authenticate each other by messagesC and D, because only the genuine tag has the subkeys K1 and K2 which generate the consistent message C with random numbers n1, n2. Similarly, only the genuine reader keeps the ID that is used to generate the response message D. In this way, the reader and the tag can achieve mutual authentication.


### 4.1.2. Tag Anonymity

The tag uses the pseudonym in the whole authentication process. The pseudonym of each tag will be updated after every successful authentication by the random numbersn1, n2. So the pseudonym from the same tag looks different at each session authentication and the attackers cannot get the real identity of the tag. Moreover, even if the attackers intercept authentication pseudonym IDS, they cannot analyze the practical information from it.


### 4.1.3. Resistance to Tracking

The data stored in the database and the tag will be updated after the successful authentication process. So the message and the response message are different at each session authentication, making it almost impossible for the attackers to track the tag. In addition, the tag uses the pseudonym which improves the difficulty of tracking.


### 4.1.4. Data Confidentiality [17]

The calculation of each value ofA,B,C, and D involves at least two secret values, including the subkey and random number. So, it is very hard to get the tag ID except for the tag itself that has K1,K2 and n1, n2.


### 4.1.5. Forward Security

After each successful session, the key andIDS value will be updated in the tag and the database. So even if the attacker achieves some session information, he cannot use it to trace back to previous communications. In addition, ULMAP makes the subkey and random number involved in the entire update process, which makes the entire update process have stronger stochastic properties. So ULMAP is forward security.


### 4.1.6. Nonreplaying

Because the value ofIDS will be updated after the successful authentication process, the response message IDS∥A∥B∥C from the same tag is different in each session authentication process. Moreover, the timestamp TR is constantly changing over time. Therefore, the attacker cannot priorly disguise information to achieve legality certification.


### 4.1.7. Non-Denial of Service (Non-DoS) [18]

When the reader starts a new session, the tag will judge whetherTR > Tt. If not, the authentication is failed. Otherwise, the authentication process will continue. Compared with all most schemes responding to the query, ULMAP can reduce the number of denial of service attacks to some extent and prevent unauthorized readers from continuing to send queries which consume lots of resources of the tag. Therefore, this scheme can resist denial of service attacks in some cases.The comparison between LMAP [19], SASI [20], and ULMAP in security is shown in Table 1. “√” means satisfaction, “×” means to dissatisfy, and “#” means satisfaction to a certain extend.Table 1
The security and functionality comparison.
Scheme
Mutual authentication and forward security
Confidentiality and anonymity
Resistance to tracking
Nonreplaying
Resistance to desynchronization attack
Non-DoS
LMAP
×
×
×
×
×
×
SASI
√
√
√
√
×
×
ULMAP
√
√
√
√
√
#It is very obvious, in Table1, that neither of SASI and LMAP can resist desynchronization and DoS attacks. However, in addition to the forward security, data confidentiality, nonreplaying, and so forth, the proposed protocol ULMAP can prevent synchronicity attacks effectively and prevent DoS attacks to some extent. In summary, ULMAP improves the security.


### 4.1.8. Synchronization

In a normal session, if the tracker heads off the last message that the database sends to the tag, the database cannot be successfully verified. Once this case happens, the tag cannot be updated, but the database has been updated successfully. So the tag and the database will lose the synchronization. However, in the ULMAP protocol, theIDS, K1, K2, used in the last session is stored in ID,IDSold,Kold1,Kold2,IDSnew,Knew1,Knew2 in the database, so that this tag is still able to finish the authentication and get the synchronization again successfully.


## 4.1.1. Mutual Authentication

The tag and the reader can authenticate each other by messagesC and D, because only the genuine tag has the subkeys K1 and K2 which generate the consistent message C with random numbers n1, n2. Similarly, only the genuine reader keeps the ID that is used to generate the response message D. In this way, the reader and the tag can achieve mutual authentication.


## 4.1.2. Tag Anonymity

The tag uses the pseudonym in the whole authentication process. The pseudonym of each tag will be updated after every successful authentication by the random numbersn1, n2. So the pseudonym from the same tag looks different at each session authentication and the attackers cannot get the real identity of the tag. Moreover, even if the attackers intercept authentication pseudonym IDS, they cannot analyze the practical information from it.


## 4.1.3. Resistance to Tracking

The data stored in the database and the tag will be updated after the successful authentication process. So the message and the response message are different at each session authentication, making it almost impossible for the attackers to track the tag. In addition, the tag uses the pseudonym which improves the difficulty of tracking.


## 4.1.4. Data Confidentiality [17]

The calculation of each value ofA,B,C, and D involves at least two secret values, including the subkey and random number. So, it is very hard to get the tag ID except for the tag itself that has K1,K2 and n1, n2.


## 4.1.5. Forward Security

After each successful session, the key andIDS value will be updated in the tag and the database. So even if the attacker achieves some session information, he cannot use it to trace back to previous communications. In addition, ULMAP makes the subkey and random number involved in the entire update process, which makes the entire update process have stronger stochastic properties. So ULMAP is forward security.


## 4.1.6. Nonreplaying

Because the value ofIDS will be updated after the successful authentication process, the response message IDS∥A∥B∥C from the same tag is different in each session authentication process. Moreover, the timestamp TR is constantly changing over time. Therefore, the attacker cannot priorly disguise information to achieve legality certification.


## 4.1.7. Non-Denial of Service (Non-DoS) [18]

When the reader starts a new session, the tag will judge whetherTR > Tt. If not, the authentication is failed. Otherwise, the authentication process will continue. Compared with all most schemes responding to the query, ULMAP can reduce the number of denial of service attacks to some extent and prevent unauthorized readers from continuing to send queries which consume lots of resources of the tag. Therefore, this scheme can resist denial of service attacks in some cases.The comparison between LMAP [19], SASI [20], and ULMAP in security is shown in Table 1. “√” means satisfaction, “×” means to dissatisfy, and “#” means satisfaction to a certain extend.Table 1
The security and functionality comparison.
Scheme
Mutual authentication and forward security
Confidentiality and anonymity
Resistance to tracking
Nonreplaying
Resistance to desynchronization attack
Non-DoS
LMAP
×
×
×
×
×
×
SASI
√
√
√
√
×
×
ULMAP
√
√
√
√
√
#It is very obvious, in Table1, that neither of SASI and LMAP can resist desynchronization and DoS attacks. However, in addition to the forward security, data confidentiality, nonreplaying, and so forth, the proposed protocol ULMAP can prevent synchronicity attacks effectively and prevent DoS attacks to some extent. In summary, ULMAP improves the security.


## 4.1.8. Synchronization

In a normal session, if the tracker heads off the last message that the database sends to the tag, the database cannot be successfully verified. Once this case happens, the tag cannot be updated, but the database has been updated successfully. So the tag and the database will lose the synchronization. However, in the ULMAP protocol, theIDS, K1, K2, used in the last session is stored in ID,IDSold,Kold1,Kold2,IDSnew,Knew1,Knew2 in the database, so that this tag is still able to finish the authentication and get the synchronization again successfully.


## 4.2. Performance and Complexity Analysis

We will compare ULMAP with SASI and LMAP in performance and complexity. In order to compare easily, assume there arem tags in the system and the length of data is L.


### 4.2.1. The Cost of Storage

To achieve the authentication, in SASI protocol, the tag stores the message(ID,(IDSnew,K1new,K2new)(IDSold,K1old,K2old)) and (ID,IDS,K1,K2) is stored in the database, so the cost of storage in the tag and database is 7L and 4mL, respectively. As it is shown in Table 2, in LMAP, the tag storage space needs 6L and the corresponding database storage space requires 6mL. But in our protocol, the cost of storage space in the tag is 5L and the cost of storage space in the database is 7mL.Table 2
The storage overhead comparison.
Scheme
Database
Reader
Tag
LMAP
6
m
l
0
6
L
SASI
4
m
l
0
7
L
ULMAP
7
m
l
0
5
LUsually, the database has more resources than the tag, so the resource of tag is more valuable. Comparing with other protocols, the ULMAP needs smaller storage space in the tag that will greatly reduce the cost of the tag and increase a little cost of storage space in the database. Therefore, the proposed protocol can greatly reduce input cost. The specific storage overhead is shown in Table2.


### 4.2.2. The Cost of Communication

The cost of communication consists of the number of interactions and the length of the communication data. From Table3, we can know that the interaction times of both SASI and LMAP are 4. Although the transmitted data is increased a little, our protocol is just transmitted three times between the reader and the tag, which are four times in other protocols. Therefore, ULMAP has a relatively low communication overhead.Table 3
The cost of communication comparison.
Scheme
The number of interactions
Total cost of communication
LMAP
4
5
L
SASI
4
5
L
ULMAP
3
7
LComparing with other protocols, the ULMAP uses the timestamp for the first time. This will make the ULMAP resist the attack of DoS to a certain extent. Moreover, the subkey and random numbers are used widely in the database and the tag in the authentication update phase. This can make the whole protocol have stronger random feature which will greatly improve the ability of resisting desynchronization and the forward security of ULMAP.


### 4.2.3. The Cost of Computation Time

In order to better compare the computation performance of different protocols in Table4, + represents AND operation, ⊕ represents the XOR operation, Rot is the displacement Rot(x,y) operation, Rot2 is two displacement Rot(x,y) operations, and T represents the pseudorandom number or timestamp.Table 4
Computation cost comparison.
Scheme
LMAP
SASI
ULMAP
Cost
⊕
,
+
,
∧
,
∨
⊕
,
+
,
∧
,
∨
,
R
o
t
⊕
,
+
,
∧
,
∨
R
o
t
2
,
M
i
x
B
i
t
sFrom Table4, it is shown that the tag in ULMAP needs one random number generation. In addition, ULMAP also needs more computation operation (like Rot, MixBits) in the tag compared with SASI and Gossamer. Although this will increase the cost of computation, the computations also become more secure and effective with it.By comparing our protocol with other schemes, it shows that our proposed protocol not only can provide mutual authentication function but also has the advantage of higher level of security and performance.


## 4.2.1. The Cost of Storage

To achieve the authentication, in SASI protocol, the tag stores the message(ID,(IDSnew,K1new,K2new)(IDSold,K1old,K2old)) and (ID,IDS,K1,K2) is stored in the database, so the cost of storage in the tag and database is 7L and 4mL, respectively. As it is shown in Table 2, in LMAP, the tag storage space needs 6L and the corresponding database storage space requires 6mL. But in our protocol, the cost of storage space in the tag is 5L and the cost of storage space in the database is 7mL.Table 2
The storage overhead comparison.
Scheme
Database
Reader
Tag
LMAP
6
m
l
0
6
L
SASI
4
m
l
0
7
L
ULMAP
7
m
l
0
5
LUsually, the database has more resources than the tag, so the resource of tag is more valuable. Comparing with other protocols, the ULMAP needs smaller storage space in the tag that will greatly reduce the cost of the tag and increase a little cost of storage space in the database. Therefore, the proposed protocol can greatly reduce input cost. The specific storage overhead is shown in Table2.


## 4.2.2. The Cost of Communication

The cost of communication consists of the number of interactions and the length of the communication data. From Table3, we can know that the interaction times of both SASI and LMAP are 4. Although the transmitted data is increased a little, our protocol is just transmitted three times between the reader and the tag, which are four times in other protocols. Therefore, ULMAP has a relatively low communication overhead.Table 3
The cost of communication comparison.
Scheme
The number of interactions
Total cost of communication
LMAP
4
5
L
SASI
4
5
L
ULMAP
3
7
LComparing with other protocols, the ULMAP uses the timestamp for the first time. This will make the ULMAP resist the attack of DoS to a certain extent. Moreover, the subkey and random numbers are used widely in the database and the tag in the authentication update phase. This can make the whole protocol have stronger random feature which will greatly improve the ability of resisting desynchronization and the forward security of ULMAP.


## 4.2.3. The Cost of Computation Time

In order to better compare the computation performance of different protocols in Table4, + represents AND operation, ⊕ represents the XOR operation, Rot is the displacement Rot(x,y) operation, Rot2 is two displacement Rot(x,y) operations, and T represents the pseudorandom number or timestamp.Table 4
Computation cost comparison.
Scheme
LMAP
SASI
ULMAP
Cost
⊕
,
+
,
∧
,
∨
⊕
,
+
,
∧
,
∨
,
R
o
t
⊕
,
+
,
∧
,
∨
R
o
t
2
,
M
i
x
B
i
t
sFrom Table4, it is shown that the tag in ULMAP needs one random number generation. In addition, ULMAP also needs more computation operation (like Rot, MixBits) in the tag compared with SASI and Gossamer. Although this will increase the cost of computation, the computations also become more secure and effective with it.By comparing our protocol with other schemes, it shows that our proposed protocol not only can provide mutual authentication function but also has the advantage of higher level of security and performance.


## 5. Conclusions

This paper proposes a new NFC mutual authentication protocol, named ULMAP. ULMAP can achieve not only mutual authentication but also complete anonymity. Moreover, the proposed scheme possesses higher security and performance. Because the database stores the new and old session private key and IDS, when the new session private key of the tag fails to update, the corresponding old private key and IDS can also be used. So the proposed protocol can effectively resist the desynchronization attack.



---

*Source: 2349149-2017-04-27.xml*