# Ultralightweight RFID Authentication Protocols for Low-Cost Passive RFID Tags

Authors: Madiha Khalid; Umar Mujahid; Najam-ul-Islam Muhammad
Journal: Security and Communication Networks
 (2019)

---

## Abstract

The field of pervasive computing especially the Internet of Things (IoT) network is evolving due to high network speed and increased capacity offered by the 5G communication system. The IoT network identifies each device before giving it access to the network. The RFID system is one of the most prominent enabling technologies for the node identification. Since the communication between the node and the network takes place over an insecure wireless channel, an authentication mechanism is required to avoid the malicious devices from entering the network. This paper presents a brief survey on the authentication protocols along with the prominent cryptanalysis models for the EPC C1G2 RFID systems. A comparative analysis is provided to highlight the common weaknesses of the existing authentication algorithms and to emphasize on the lack of security standardization for the resource constraint IoT network perception layer. This paper is concluded by proposing an ultralightweight protocol that provides Extremely Good Privacy (EGP). The proposed EGP protocol avoids all the pitfalls highlighted by the cryptanalysis of the existing authentication protocols. The incorporation of the novel ultralightweight primitives, Per-XOR(Px) and Inverse Per-XOR (Px-1), makes the protocol messages more robust and irreversible for all types of adversaries. A comprehensive security analysis illustrates that the proposed protocol proves to be highly resistive against all possible attack scenarios and ensures the security optimally.


---

## Body

## 1. Introduction

The concept of creating low-cost, reliable, and secure Internet of Things (IoT) networks for current and future applications is evolving by the virtue of high network speed and increased capacity offered by the5th generation communication system. The IoT network consists of interrelated computing devices with unique identification, deployed in the environment to collect, process, and share the information, in order to facilitate the measurement of changes in the surroundings and to react independently primarily without human interaction [1–4]. The data collected by the network is also processed to generate valuable information that can be used to enhance the user experience in future [5]. The IoT platform is being used in various fields to achieve purposeful objectives such as logistics [6], smart cities [7], and supply chain management [8].The IoT network initially identifies the electronic devices (nodes) before giving them access to the network. The Radio Frequency Identification (RFID) system is emerging as an enabling technology for the node discovery due to the features such as high speed, long range, and nonline of sight scanning [4]. The RFID enabled IoT networks are being preferred in various surveillance, monitoring, and healthcare applications. Table 1 highlights some of the prominent applications reported in the literature.Table 1
RFID enabled IoT applications.
System Function Smart Home Mobile RFID based IoT system [9] This is a smart home service system to benefit the user in terms of cost, energy consumption and ease.  RFID & IoT for attendance monitoring system [10] This is a real time attendance monitoring system that can be accessed by various parties, i.e., teachers, students and parents.  Harvard hybrid system [11, 12] The system uses the RFID tags to track equipments, beds, patients and ICU babies.  Positive patient identification system [13] The system facilitates the patient identification and speed up access to the patient’s data.  Intel transfusion system [14] This system identifies blood bags, recipients and staff. The purpose of this system is to enhance the safety of the blood transfusion.The architecture of the RFID enabled IoT network is composed of three components: the RFID system, the IoT middleware, and the Internet [15]. The RFID system facilitates the node identification and the data collection. The data gathered from the environment under observation is processed by the IoT middleware. The IoT middleware also acts as a gateway to the external Internet [16].The architecture of the RFID system embedded in an IoT network consists of three main components; the Electronic Product Code (EPC) tag, the reader, and the database. The tag is a low-cost electronic chip with the unique identification number (ID). The reader identifies each tag associated with the system by receiving the ID over the wireless channel. The database supports the reader in an identification process by storing attributes of all the tags affiliated with the RFID system [17].The EPC standards have segregated the tags into classes based on their functionality. The description of each EPC class is given in Table2 [18].Table 2
EPC classification of RFID tags.
Class Description Class 5 Class 5 tags are essentially active readers. They have the ability to communicate with all the EPC standard classes.  Class 4 Class 4 tags are active in nature. They can communicate with the reader and other tags by using peer to peer communication model.  Class 3 Class 3 tags are semi passive tags that can support broadband communication.  Class 2 Class 2 tags are the passive tags with extended functionality such as memory and computational resources.  Class 1/0 Class 1/0 tags are basic passive identity tags with limited resources.In the RFID enabled IoT networks, the node is identified by communicating the tag’sID to the reader over an insecure wireless channel. Therefore, the system is prone to many security and privacy threats [19]. A mutual authentication mechanism is an inevitable part of the tag identification process. In this paper, a brief survey on the existing mutual authentication protocols and the prominent cryptanalysis models for the EPC Class 1 Generation 2 (C1G2) RFID systems is presented. A comparative security analysis among the prominent protocols has been drawn to highlight some of the common weaknesses of the existing authentication algorithms for the resource constraint RFID systems. The paper also proposes the Extremely Good Privacy (EGP) protocol. The comprehensive security analysis of the EGP protocol ensures its security claims and robustness against all existing cryptanalysis models. The EPC C1G2 tags are the key component of the low-cost RFID systems due to characteristics like small size, low cost, and unlimited lifespan [20]. Other features of the EPC C1G2 identification system are enumerated as follows [18]:(i)
Operating frequency: 860 MHz-960 MHz(ii)
Memory capacity: 96-256 bits(iii)
Field programmable(iv)
Reprogrammable(v)
Communication: 640Kbits/s(vi)
Reads: 1700 tags/secThe rest of the paper is organized as follows: Section2 discusses the Ultralightweight Mutual Authentication Protocols (UMAPs) for the resource constraint RFID systems followed by Section 3 that describes multiple cryptanalysis models used for the security and privacy evaluation of the UMAPs. This section also presents a comparative analysis of the prominent UMAPs based on their strengths to provide Confidentiality, Integrity, Availability, and Authentication (CIAA) services. The EGP protocol is proposed in Section 4 along with the detailed cryptanalysis report. Finally, the paper is concluded in Section 5.


## 2. Ultralightweight Mutual Authentication Protocols

The node authentication mechanism during the identification process prevents the malicious users from entering the network through the perception layer. In 2007, Chien [21] divided the authentication protocols in four categories which are defined as follows:(1)
Heavyweight: these protocols incorporate the classical cryptographic suits such as hash functions and private and public key cryptography.(2)
Middleweight: this category includes the protocols that can support one-way hash functions and pseudorandom-number generators only.(3)
Lightweight: these protocols can support the lightweight functions such as Cyclic Redundancy Checks (CRCs) and lightweight pseudorandom number generators.(4)
Ultralightweight: this class allows the incorporation of simple bitwise logical function only, for the protocol design.Table3 presents a relationship among the protocol categorization and the EPC classes supported by some prominent examples.Table 3
Mutual authentication protocol classification.
Protocol Classification EPC Class association Examples Heavyweight Class 5/4 Godor and Imre [22], Liu et al [23]  Middleweight Class 3 Wang et al [24], Chou [25], Zhang and Qi [26]  Lightweight Class 2 Lee et al [27], Liao et al [28]  Ultralightweight Class 1/0 Tewari and Gupta [29], SLAP [30], KMAP [31]For low-cost systems, the silicon-based area of the EPC tags should be kept minimum to reduce the cost. Typically, an EPC C1G2 tag consists of32Kbits response buffer [32] and can support maximum 4K Gate Equivalent (GE) for the crypto based operations. One gate equivalent corresponds to the area required for the fabrication of two input NAND gate [33]. Hence smaller GE for the authentication protocol implementation corresponds to the lesser cost overhead associated with the security-based operations.Table3 suggests that for C1G2 tags implementation of the UMAP is the only cost-effective option for the node verification at the identification stage. Numerous UMAPs have been presented over the last decade. This section describes the general structure of the UMAPs along with a brief survey of the existing protocols. Since 2006, more than thousand protocols have been proposed; however the basic working principle of these protocols remains the same. The UMAPs ensure that both the entities, i.e., the tag and the reader, are authentic components of an identification system with the help of a static and unique ID along with the pseudoidentification number and the keys (IDS,K) which are dynamic in nature. The dynamic variables update their status on both sides after every successful authentication session whereas the static ID remains constant. The mutual authentication process mainly consists of four steps which are as follows [34]:(1)
Tag identification: the tag receives a request for the latest identity pseudonymIDS after entering the communication range of the reader. The reader identifies the tag by retrieving the associated identification number and the keys from the database with the help of IDS.(2)
Reader authentication: after the tag authentication, the reader generates a private key for the authentication session and transmits messageX to the tag. The message X consists of an encrypted version of the private key and the reader authentication challenge message. The reader’s identity is verified if the response calculated at the tag’s side is equal to the received challenge message.(3)
Tag authentication: the successful reader identity verification leads to the calculation and the transmission of the tag authentication challenge messageY for the valid reader.(4)
Dynamic variable update: the mutual authentication of communicating parties is followed by the dynamic variable updating process on both sides.The block diagram of the generalized UMAP is presented Figure1. The features that differentiate the UMAPs are the tag’s memory architecture and the protocol’s primitives. The UMAPs can be classified into three categories based on the nature of the operators used for the calculation of challenge/response messages. Description of each category along with the examples of prominent protocols is as follows.Figure 1
Flow diagram of generalized UMAP.


### 2.1. UMAPs with Triangular Functions

In 2006, Peris-Lopez [35–37] laid the foundation of the ultralightweight cryptography. The main idea was to use the triangular functions such as bitwise AND,OR,XOR, and modularaddition for the encryption of public messages which are being communicated among the resource constraint devices. The prominent UMAPs with triangular functions are Lightweight Mutual Authentication Protocol (LMAP) [35], Minimalistic Mutual Authentication Protocol (M2AP) [36], and Efficient Mutual Authentication Protocol (EMAP) [37].


#### 2.1.1. Lightweight Mutual Authentication Protocol (LMAP)

The LMAP laid the foundation of UMAPs and falls under the umbrella of the triangular UMAPs. The memory architecture of the tag and the reader implementing the LMAP is given in Table4. The protocol executes in following steps:(1)
The reader sends the “Hello” message to the tag.(2)
The tag replies withIDS to the reader. This IDS acts as an index in the database to locate the keys and the ID related to the tag. If the required data is not found, the protocol is terminated; otherwise it moves to next step.(3)
In step (3), the reader generates two pseudorandom numbersn1and n2. These random numbers are used for the calculation of the messages A,B and C.(1)A=IDS⊕K1⊕n1(2)B=IDS∨K2⊕n1(3)C=IDS+K2+n2Finally, X=A∥B∥C is transmitted to the tag.(4)
The tag extractsn1 and n2 from the messages A and C, respectively. The message B is a challenge token for the reader authentication. After successful reader authentication, the protocol moves to step (5).(5)
The tag generates and transmits messageD=Y. The message D has two purposes: (a) concealed transfer of the tag’s ID; (b) the tag authentication.(4)D=IDS+ID⊕n1⊕n2After the transmission of the message D, the dynamic variables at the tag’s end are updated using following equations:(5)IDSNEW=IDS+n2⊕K4⊕ID(6)K1NEW=K1⊕n2⊕K3+ID(7)K2NEW=K2⊕n2⊕K4+ID(8)K3NEW=K3⊕n1⊕K1+ID(9)K4NEW=K4⊕n1⊕K2+ID(6)
The reader receives the messageD, authenticates the tag, and updates the dynamic variables using (5)-(9). The process of updating dynamic variables on the reader’s side only takes place in case of successful mutual authentication.Table 4
Memory architecture of triangular UMAPs.
Protocol Storage Location Reader Tag LMAP ( I D , I D S , K 1 , K 2 , K 3 , K 4 ) ( I D , I D S , K 1 , K 2 , K 3 , K 4 ) M2AP EMAPThe flow diagram of the LMAP is given in Figure2. Despite being resource efficient, the LMAP is a weak protocol in terms of structure and equations. The triangular functions alone are unable to conceal the tag’s secrets in public messages due to their imbalance nature. Several cryptanalysis attacks on the LMAP have proved that the protocol cannot be used as a standard for the RFID authentication purposes.Figure 2
Block diagram of LMAP.


#### 2.1.2. Minimalistic Mutual Authentication Protocol (M2AP)

The second protocol from the triangular UMAP family is the M2AP. This protocol is similar to the LMAP in terms of the tag’s memory architecture and the protocol’s primitives. The basic difference between the two protocols is the composition of public message Y. The memory architecture of the tag implementing the M2AP is given in Table 4. The step by step execution of the protocol is elaborated as follows:(1)
The reader “pings” the tag, detected in its vicinity.(2)
The tag responds with theIDS which acts as an index to locate the data associated with the tag in the database for successful tag identification.(3)
After the tag identification, the reader generates two pseudorandom numbersn1 and n2. The reader then computes and transmits challenge message X=A∥B∥C to the tag.(10)A=IDS⊕K1⊕n1(11)B=IDS∧K2∨n1(12)C=IDS+K3+n2(4)
The tag extractsn1 and n2 from A and C, respectively, and verifies the identity of the reader by calculating a response for message B. After successful reader authentication, the tag calculates and transmits challenge message Y=D∥E.(13)D=IDS∨K4∧n2(14)E=IDS+ID⊕n1The message D is used for the tag authentication whereas the message E is used for the ID communication.(5)
After successful mutual authentication, the dynamic memory on both sides is updated using the following equations:(15)IDSNEW=IDS+n1⊕n2⊕ID(16)K1NEW=K1⊕n2⊕K3+ID(17)K2NEW=K2⊕n2⊕K4+ID(18)K3NEW=K3⊕n1⊕K1+ID(19)K4NEW=K4⊕n1⊕K2+IDThe block diagram of the protocol is given in Figure 3. The cryptanalysis of M2AP was similar to that of LMAP due to similarity in composition of public messages equations and memory architectures.Figure 3
Block diagram of M2AP.


#### 2.1.3. Efficient Mutual Authentication Protocol (EMAP)

The EMAP is the third most prominent protocol from the triangular class. The primitives used for the encryption of communication between the tag/reader pair areAND,OR, and XOR. The memory architecture of the tag implementing the EMAP is given in Table 4. The working principle of the protocol is as follows:(1)
The tag receives a “Hello” message from the reader as it enters its communication range.(2)
The reader receives theIDS, which is used for the tag identification by locating the data associated with the communicating tag in the system’s database.(3)
Once the tag is identified, the reader generates the random numbers and sends messageX=A∥B∥C to the tag.(20)A=IDS⊕K1⊕n1(21)B=IDS∨K2⊕n1(22)C=IDS⊕K3⊕n2(4)
The tag extractsn1 from message A and authenticates the reader by calculating the response for challenge message B. After successful reader authentication the tag extracts n2 from the message C, to calculate and send challenge message Y=D∥E.(23)D=IDS∧K4⊕n2(24)E=IDS∧n1∨n2⊕ID⊕K1⊕K2⊕K3⊕K4(5)
The authentication session ends by updating the dynamic memory on both sides.(25)IDSNEW=IDS⊕n2⊕K1(26)K1NEW=K1⊕n2⊕ID1:48∥FpK4∥FpK3(27)K2NEW=K2⊕n2⊕FpK4∥FpK4∥ID49:96(28)K3NEW=K3⊕n1⊕ID1:48∥FpK4∥FpK2(29)K4NEW=K4⊕n1FpK3∥FpK1∥ID49:96The function Fp(x) generates a 24bit version of 96bit input x. The input is divided into twenty-four groups by combining 4bits in each group. The final output is obtained by taking bitwise XOR of all the entities present in each group and concatenating the result. The block diagram of the protocol is given in Figure 4.Figure 4
Block diagram of EMAP.


### 2.2. UMAP with Single Nontriangular Function

The resource limitation of EPC C1G2 tags confines the computational cost of the UMAPs to4K GE. Initially, the UMAPs only used the triangular functions for the calculation of the challenge/response messages. But triangular protocols were prone to multiple security attacks due to the lack of diffusion in the public messages. The reason behind the inability of encrypted string to conceal the secret values associated with the tag was the imbalance nature of the protocol’s operators.In 2007, Chien [21] introduced the idea of the ultralightweight nontriangular primitive as the protocol’s operator. The use of single nontriangular primitive improved the strength of the UMAPs; however the cryptanalysis of nontriangular UMAPs still highlighted weaknesses in the protocol structure and operators. Some of the prominent UMAPs with single nontriangular primitives are Strong Authentication Strong Integrity (SASI) protocol [21], Gossamer’s protocol [38], and Yeh et al. protocol [39].


#### 2.2.1. Strong Authentication Strong Integrity Protocol

The SASI protocol was the first protocol in the field of nontriangular UMAPs. The nontriangular function used in the SASI protocol is the rotation function (Rot(x,y)). The rotation function has two definitions: left rotation of x by the hamming weight of y and left rotation of xbymodofy. For this section, we will consider hamming weight-based rotation function. The memory architecture of the tag implementing the SASI protocol is elaborated in Table 5. The reason behind storing the pair of latest dynamic variables was to provide protection against Denial of Service (DoS) attacks. The working principles of the SASI protocol are as follows:(1)
The reader requests the tag for a pseudoidentification number.(2)
The tag transmits its latestIDS. If the received IDS is found in the database, the protocol proceeds further otherwise the reader requests the tag for the IDS from the previous successful authentication session (IDSold). The successful tag identification leads to the step (3).(3)
The reader generates two random numbersn1 and n2. The dynamic variables and random numbers are used by the reader to generate and transmit X=A∥B∥C.(30)A=IDS⊕K1⊕n1(31)B=IDS∨K2⊕n2(32)K1-=RotK1⊕n2,K1(33)K2-=RotK2⊕n1,K2(34)C=K1⊕K2-+K1-⊕K2(4)
The pseudorandom numbersn1 and n2 are concealed in and communicated to the tag via message A and B, respectively. The message C is used for the reader authentication.(5)
After successful reader authentication, the tag transmits messageY=D for the tag authentication and the ID transmission.(35)D=K2-+ID⊕K1⊕K2∨K1-(6)
After mutual authentication, the dynamic variables on both sides are updated using following equations:(36)IDSold=IDS,K1old=K1,K2old=K2(37)IDS=IDSold+ID⊕n2⊕K1-,K1=K1-,K2=K2-The flowchart of the SASI protocol is given in Figure 5.Table 5
Memory architectures of UMAPs with single nontriangular function.
Protocol Storage Location Reader Tag SASI ( I D , I D S , K 1 , K 2 ) ( I D , I D S , K 1 , K 2 , I D S o l d , K 1 o l d , K 2 o l d ) Gossamer’s Protocol ( I D , I D S , K 1 , K 2 ) ( I D , I D S , K 1 , K 2 , I D S o l d , K 1 o l d , K 2 o l d ) Yeh et al.’s Protocol ( I D , I D S , I D S o l d , K , K o l d ) ( I D , I D S , K )Figure 5
Block diagram of SASI protocol.


#### 2.2.2. Gossamer’s Protocol

In 2008, Peris-Lopez presented nontriangular UMAPs to overcome the weaknesses of the SASI protocol. In the Gossamer’s protocol, the memory architecture of the system was enhanced by saving the latest copy of dynamic variables on the tag’s side. The memory architecture of the protocol is given in Table5. The nontriangular primitive of the Gossamer’s protocol is mix bit function (mixbit(a,b)). The mix bit function consists of two subfunction: the rotation and the modular addition function. These subfunctions are used independently and in collaborative manner to calculate the challenge/response messages. The working principle of x=mixbit(a,b) is elaborated in Figure 7.The protocol executes in five steps which are defined as follows:(1)
The reader sends a request for theIDS to the tag present in its vicinity.(2)
The reader tries to locate the tags information by searching the database with the help of the receivedIDS. The tag is identified if its information is found in the database.(3)
The reader generates pseudorandom private keysn1 and n2. The reader then sends message X=A∥B∥C to the tag.(38)A=RotRotIDS+K1+π+n1,K2+K1,K1(39)B=RotRotIDS+K2+π+n2,K1+K2,K2(40)n3=Mixbitn1,n2(41)K1∗=RotRotn2+K1+π+n3,n2+K2⊕n3,n1⊕n3(42)K2∗=RotRotn1+K2+π+n3,n1+K1+n3,n2+n3(43)n1′=Mixbitn3,n2(44)C=RotRotn3+K1∗+π+n1′,n3+K2∗⊕n1′,n2⊕n1′(4)
The reader is authenticated by generating a response to the messageC. After that, the tag calculates and transmits the challenge message Y=D.(45)D=RotRotn2+K2∗+ID+n1′,n2+K1∗+n1′,n3+n1(5)
The dynamic variable on both sides are updated after a successful mutual authentication.(46)IDSold=IDS;K1old=K1;K2old=K2(47)n2′=Mixbitn1′,n3(48)IDS=RotRotn1′+K1∗+IDS+n2′,n1′+K2∗⊕n2′,n3⊕n2′(49)K1=RotRotn3+K2∗+π+n2′,n3+K1∗+n2′,n1′+n2′(50)K2=RotRotIDSnew+K2∗+π+K1new,IDSnew+K1∗+K1new,n2′+K1newThe constantπ used in the protocol assumes the value 0x3243F6A8885A308D313198A2. The block diagram of the Gossamer’s protocol is presented in Figure 6.Figure 6
Block diagram of Gossamer’s protocol.Figure 7
m i x b i t ( a , b ) algorithm.


#### 2.2.3. Yeh et al. Protocol

In 2010, Yeh et al. [39] proposed a process oriented UMAP. The feature that differentiates this protocol from its predecessors is the DoS avoidance mechanism. In this protocol, the pairs of latest dynamic variables are stored at the reader side instead of the tag. The reader also maintains a flag to identify whether the tag/reader pair is fully synchronized or not. The nontriangular function used in the protocol is the rotation function (Rot(a,b)). The memory architecture of the UMAP is given in Table 5. The working principle of the Yeh et al. protocol is as follows: the protocol is the rotation function (Rot(a,b)). The memory architecture of the UMAP is as follows:(1)
The reader initiates the communication by sending a “Hello” message to the tag.(2)
As a response, the tag transmits theIDS stored in its dynamic memory.(3)
After successful tag identification through the database, the reader generates two pseudorandom numbersn1 and n2. If the IDS=IDSnew, the reader sets an internal flag f=0; otherwise the flag’s value sets to 1, the key K updates and becomes equal to the tag’s ID. After key updation, the reader calculates and sends message X=A∥B∥C∥f to the tag.(51)A=IDS⊕K⊕n1(52)B=IDS∨K⊕n2(53)K∗=RotK⊕n2,n1(54)C=K∗⊕n1+n2(55)f=flagbit;f=0ifIDS=IDSNEWf=1ifIDS=IDSOLD(4)
Upon receiving the challenge message, the tag updates the value of the keyK based on the flag status. After that n1 and n2 are extracted and the reader is authenticated.(5)
The successful reader verification leads to the calculation and transmission of the tag authentication challenge messageD.(56)K¨∗=RotK⊕n1,n2(57)D=K¨∗⊕n2+n1(6)
In case of successful mutual authentication, the dynamic memory on both sides is updated.(58)IDSNew=IDS+ID⊕K¨∗⊕n1⊕n2(59)KNew=K∗The block diagram of the Yeh et al. protocol is given in Figure8.Figure 8
Block diagram of Yeh et al. protocol.


### 2.3. UMAPs with Hybrid Nontriangular Function

The cryptanalysis of the UMAPs with single nontriangular functions proved the inability of the protocols to provide Confidentiality, Integrity, Availability and Authentication (CIAA) to the communicating parties. In order to further improve the security, the concept of using hybrid nontriangular functions was introduced. This idea improved the security and privacy services offered by the UMAPs. There are many hybrid nontriangular UMAPs available in the literature. In this subsection, the protocols under consideration are RFID Authentication Protocol with Permutation (RAPP) [4], RFID Authentication Protocol for Low cost Tags (RAPLT) [40], Robust Confidentiality Integrity and Authentication (RCIA) protocol [41], and Succinct and Lightweight Authentication Protocol (SLAP) [30].


#### 2.3.1. RFID Authentication Protocol with Permutation (RAPP)

The RAPP protocol was different from previously presented UMAPs, in terms of the primitives used for encryption and the sequence of interaction between the tag and the reader. The protocol only used three operations, i.e.,XOR, rotation (Rot(x,y)) and permutation (Per(x,y)).TheRot(x,y) corresponds to the left rotation of x by the hamming weight of y. The description of permutation function (z=per(x,y)) is as follows. Let z be a L-bit word and zi be the ith bit of z where 1≤i≤L, and z1 and zL be the LSB and MSB of the word z, respectively. Suppose x and y are two L-bit words and hamming weight of y is m. Moreover yi=1 if i∈I1={km,km-1…k1} and yi=0 if i∈I0={kL,kL-1…km+1}.(60)km>km-1>⋯>k1kL>kL-1>⋯>km+1The permutation ofx according to y, i.e., per(x,y) is equal to(61)Perx,y=xkm,xkm-1…xk1,xkL,xkL-1…xkm+1Unlike conventional sequence of interaction, the dynamic memory of the tag is updated after getting a confirmation message of successful mutual authentication of the tag/reader pair. The aim of this message was to make the protocol resistant to the desynchronization attacks. The memory architecture of the protocol is given in Table6 and the detail description of the protocol is as follows:(1)
The tag receives a “Hello” message from the reader as soon as it enters its vicinity.(2)
The tag responds with the value ofIDS stored in its dynamic memory. The reader identifies the tag by retrieving the information indexed by the IDS value in the database.(3)
After successful tag identification, the reader generates a random numbern1 and sends challenge message X=A∥B to the tag.(62)A=PerK2,K1⊕n1(63)B=PerK1⊕K2,Rotn1,n2⊕Pern1,K1(4)
The tag verifies the reader’s identity and sends the challenge messageY=C to the reader.(64)C=Pern1⊕K1,n1⊕K3⊕ID(5)
In case of successful mutual authentication, the reader updates the dynamic variables, generates another random numbern2, and sends the mutual authentication verification message D∥E to the tag.(65)D=PerK3,K2⊕n2(66)E=PerK3,Rotn2,n2⊕Pern1,K3⊕K2(6)
The tag updates its dynamic memory after verifying the origin of messageD∥E.(67)IDSNew=PerIDS,n1⊕n2⊕K1⊕K2⊕K3(68)K1New=PerK1,n1⊕K2(69)K2New=PerK2,n2⊕K1(70)K3New=PerK3,n1⊕n2⊕IDSTable 6
Memory architecture of UMAPs with hybrid nontriangular functions.
Protocol Storage Location Reader Tag RAPP ( I D , I D S , K 1 , K 2 , K 3 , I D S o l d , K 1 o l d , K 2 o l d , K 3 o l d ) ( I D , I D S , K 1 , K 2 , K 3 ) RAPLT ( I D , I D S , K 1 , K 2 , I D S o l d ) ( I D , I D S , K 1 , K 2 , I D S o l d ) RCIA ( I D , I D S , K 1 , K 2 , I D S o l d , K 1 o l d , K 2 o l d ) ( I D , I D S , K 1 , K 2 , I D S o l d , K 1 o l d , K 2 o l d ) SLAP I D , I D S N E W , K 1 N E W , K 2 N E W , I D S O L D , K 1 O L D , K 2 O L D I D , I D S N E W , K 1 N E W , K 2 N E W , I D S O L D , K 1 O L D , K 2 O L DThe block diagram of the protocol is given in Figure9.Figure 9
Block diagram of RAPP protocol.


#### 2.3.2. RFID Authentication Protocol for Low Cost Tags (RAPLT)

In 2013, Jeon and Yoon improved the permutation function and proposed two new nontriangular function, i.e., Merge(Mer(a,b,c,d)) and separate (Sep(d,c,b,,a)) operations in RFID Authentication Protocol for Low cost Tags (RAPLT). These operations are considered to be more reliable and secure compared to the permutation function.Assumea and b are L bit numbers whereas c and d are 2L bit strings. The formation of a,b,c,d and pseudocode for Mer(a,b,c,d) and Sep(d,c,b,,a) operations are given in Figure 10.Figure 10
Merge and separate operate.Both operations have inverse relation and are extremely lightweight in nature. In RAPLT protocol, both the tag and the reader stores a pair of the latestIDS, the latest keys and the tag’s ID. The working principle of the RAPLT protocol is as follows:(1)
The reader initiates the protocol by sending a “Hello” message to the tag.(2)
As a response, the tag sends the index pseudonym(IDS) for the tag identification.(3)
After the successful tag identification throughIDS, the reader generates two random numbers (n1,n2) and computes X=A1∥A2∥B3.(71)N1=n1⊕ID;N2=n2⊕IDS(72)MerN1,N2·K1∥K2,A1∥A2(73)M1=ID⊕n1⊕K2;M2=IDS⊕n2⊕K1(74)SepM1,M2·K1∥K2,B1∥B2(75)B3=B1⊕B2(4)
The tag authenticates the reader by generating a response for the messageB3. A successful reader verification leads to the calculation and transmission of Y=C3.(76)MerK1,K2,K1∥K2,K′1∥K′2(77)Mern2,N1,K′1∥K′2,C1∥C2(78)C3=C1⊕C2(5)
The tag authentication is followed by theIDS update on both sides.(79)IDSNEW=n1The flow diagram of the RAPLT protocol is given in Figure11.Figure 11
Block diagram of RAPLT.


#### 2.3.3. Robust Confidentiality Integrity and Authentication Protocol (RCIA)

The Robust Confidentiality Integrity and Authentication (RCIA) protocol is designed on the theme of the RAPP protocol. This protocol is associated with hybrid category of the UMAPs as it uses two nontriangular functions, i.e., rotation(Rot(x,y)) and recursive hash (Rh(x)). The working principle of the recursive hash (Rh(x)) functions consists of following steps:(i)
Considerx as an L bit string and decimate the input x into k chunks with equal numbers of bits per chunk. (#ofbitsperchunk=L/k).(ii)
Assume a seed values from the range [0,k-1].(iii)
The seeds calculated in above step selects the corresponding memory block (ks) of the decimated string x.(iv)
Final answer of recursive hash function is obtained by concatenating the results of following operations.
(a)
TakeXOR between the selected memory block ks and all the other blocks except the block itself.(b)
Left rotate the blockks by the hamming weight of itself (Rotks,ks).For efficient hardware implementation, the96bit input of the recursive hash function is decimated into k=12 chunks, each containing 8bits. Both the tag and the reader store seven Lbits strings associated with the tag. These numbers are ID,(IDS,K1,K2) and (IDSold,K1old,K2old). The RCIA protocol executes in five steps which are as follows:(1)
The reader sends a “Hello” message to the tag.(2)
The tag sendsIDS to the reader. If the value is found in the database, the protocol proceeds otherwise the reader requests for IDSold and matches it with the database value. The protocol proceeds to the next step only when the received IDS is found in the database.(3)
The reader generates random numbersn1 and n2. It also calculates R=n1⊕n2. This value is used to find the seed value. The equation for seed calculation is s=Rmod⁡k. The calculation of seed value leads to calculation and transmission of X=A∥B∥C messages.(80)A=RotIDS,K1⊕n1(81)B=RotIDS∧n1,K2∧K1⊕n2(82)R=n1⊕n2;s=Rmod⁡k(83)K1∗=RotRhK2,Rhn1∧K1(84)K2∗=RotRhK1,Rhn2∧K2(85)C=RotRhK1∗,RhK2∗∧RotRhn1,Rhn2(4)
The messageC is used for the reader authentication. After one sided successful authentication, the tag updates its dynamic variables and sends the message D.(86)D=RotRhID,K1∗∧RotRhK2∗,Rhn2⊕IDS(5)
The reader uses the stringD for the tag authentication after which the dynamic variables also updates on the reader’s side. The update equations are as follows:(87)IDSNEW=RotRhIDS⊕n2,n1(88)K1NEW=K1∗;K2NEW=K2∗Figure12 shows the block diagram of the RCIA protocol.Figure 12
Block diagram of RCIA protocol.


#### 2.3.4. Succinct and Lightweight Authentication Protocol (SLAP)

In 2016, an ultralightweight authentication protocol named Succinct and Lightweight Authentication Protocol (SLAP) was proposed. The SLAP algorithm is composed of three operators, i.e.,XOR, rotation (Rot(a,b)), and Conversion (Conv(a,b)) function. These functions are lightweight with respect to the implementation cost and are appropriate for the passive electronic chips. The conversion function is the main feature of the protocol that guarantees irreversibility, confidentiality, full confusion, and low complexity.The conversion function(Conv(a,b)) consists of three subfunctions. Suppose the size of input strings (a,b) is L bits, i.e., (89)a=aLaL-1aL-2…a1;b=bLbL-1bL-2…b1The description of these functions is as follows:(i)
Grouping. The inputs a and b are divided into segments based on the hamming weight and a threshold t. Consider the input a; based on the hamming weight m=Hw(a) divide the input string into two parts, i.e., (a1=aLaL-1…am+1) and (a2=amam-1…a1). Continue the segmentation process based on hamming weight until the smallest segment size becomes equal to the threshold value t. The input string b is also segmented based on n=hw(b) and the threshold t. The respective segments are concatenated to form the output (a′,b′) of grouping function.(ii)
Rearrange. In this step, the regrouping of a′ and b′ bits takes place. As the length of input strings is same, exchanging the grouping form between of a′ and b′ gives two L-bit numbers. Finally, each subgroup is left rotated by its hamming weight. The output of rearrange function (a′′,b′′) is the shuffled version of a and b.(iii)
Composition. The final output of conversion function is obtained by taking XOR of the shuffled version of a and b, i.e., c=a′′⊕b′′.The RFID system implementing the SLAP stores the latest pair of dynamic variables on both communicating ends. The working principle of the protocol is as follows:(1)
The tag receives a “hello” message from the reader after entering its vicinity.(2)
The tag responds with its identity pseudonymIDS. This value is used for the tag identification at the reader’s side.(3)
After successful identification, the reader generates a random numbern and conceal it in the message A. The reader also generates a challenge message B. The reader transmits message A along with left or right half of B based on Hw(B). If Hw(B)=odd, X=A∥Bl; otherwise X=A∥Br.(90)A=ConvK1,K2⊕n(91)B=ConvRotK1,n,K1⊕K2⊕RotConvK2,K2⊕n,K1(4)
The tag authenticates the reader by generating a response to messageB. After successful reader authentication, the tag calculates the message C and transmits the left or right half of C based on Hw(C). If Hw(C)=odd, Y=Cl; otherwise Y=Cr.(92)C=ConvConvB,K1NEW,ConvK1NEW,K2NEW⊕n⊕ID(5)
After identity verification, the dynamic variables of each side are updated using following equation:(93)IDSNEW=ConvIDS,n⊕BLorR∥CLorR(94)K1NEW=ConvK1,n⊕K2;K2NEW=ConvK2,n⊕K1The block diagram of the SLAP is given in Figure13.Figure 13
Block diagram of SLAP.A brief survey on the existing protocols proves that increase in computational complexity of the authentication mechanism improves the CIAA capabilities of the protocol at the cost of increased gate equivalents. Section3 presents a set of eminent cryptanalysis models that are being used to evaluate the security and the privacy features of the UMAPs. The literature review shows that almost all the existing UMAPs have been subjected to multiple cryptanalysis attacks. The unavailability of secure and reliable UMAP for RFID enabled IoT networks is one of the major challenges in the standardization of the secure architecture for the resource constraint IoT network perception layer. The subsequent sections present a comprehensive security analysis model to evaluate the strengths of the RFID node authentication protocols, the CIAA analysis of the existing UMAPs based on the presented model, and a secure and reliable UMAP termed as Extremely Good Privacy (EGP) protocol for the authentication of resource constraint IoT nodes.


## 2.1. UMAPs with Triangular Functions

In 2006, Peris-Lopez [35–37] laid the foundation of the ultralightweight cryptography. The main idea was to use the triangular functions such as bitwise AND,OR,XOR, and modularaddition for the encryption of public messages which are being communicated among the resource constraint devices. The prominent UMAPs with triangular functions are Lightweight Mutual Authentication Protocol (LMAP) [35], Minimalistic Mutual Authentication Protocol (M2AP) [36], and Efficient Mutual Authentication Protocol (EMAP) [37].


### 2.1.1. Lightweight Mutual Authentication Protocol (LMAP)

The LMAP laid the foundation of UMAPs and falls under the umbrella of the triangular UMAPs. The memory architecture of the tag and the reader implementing the LMAP is given in Table4. The protocol executes in following steps:(1)
The reader sends the “Hello” message to the tag.(2)
The tag replies withIDS to the reader. This IDS acts as an index in the database to locate the keys and the ID related to the tag. If the required data is not found, the protocol is terminated; otherwise it moves to next step.(3)
In step (3), the reader generates two pseudorandom numbersn1and n2. These random numbers are used for the calculation of the messages A,B and C.(1)A=IDS⊕K1⊕n1(2)B=IDS∨K2⊕n1(3)C=IDS+K2+n2Finally, X=A∥B∥C is transmitted to the tag.(4)
The tag extractsn1 and n2 from the messages A and C, respectively. The message B is a challenge token for the reader authentication. After successful reader authentication, the protocol moves to step (5).(5)
The tag generates and transmits messageD=Y. The message D has two purposes: (a) concealed transfer of the tag’s ID; (b) the tag authentication.(4)D=IDS+ID⊕n1⊕n2After the transmission of the message D, the dynamic variables at the tag’s end are updated using following equations:(5)IDSNEW=IDS+n2⊕K4⊕ID(6)K1NEW=K1⊕n2⊕K3+ID(7)K2NEW=K2⊕n2⊕K4+ID(8)K3NEW=K3⊕n1⊕K1+ID(9)K4NEW=K4⊕n1⊕K2+ID(6)
The reader receives the messageD, authenticates the tag, and updates the dynamic variables using (5)-(9). The process of updating dynamic variables on the reader’s side only takes place in case of successful mutual authentication.Table 4
Memory architecture of triangular UMAPs.
Protocol Storage Location Reader Tag LMAP ( I D , I D S , K 1 , K 2 , K 3 , K 4 ) ( I D , I D S , K 1 , K 2 , K 3 , K 4 ) M2AP EMAPThe flow diagram of the LMAP is given in Figure2. Despite being resource efficient, the LMAP is a weak protocol in terms of structure and equations. The triangular functions alone are unable to conceal the tag’s secrets in public messages due to their imbalance nature. Several cryptanalysis attacks on the LMAP have proved that the protocol cannot be used as a standard for the RFID authentication purposes.Figure 2
Block diagram of LMAP.


### 2.1.2. Minimalistic Mutual Authentication Protocol (M2AP)

The second protocol from the triangular UMAP family is the M2AP. This protocol is similar to the LMAP in terms of the tag’s memory architecture and the protocol’s primitives. The basic difference between the two protocols is the composition of public message Y. The memory architecture of the tag implementing the M2AP is given in Table 4. The step by step execution of the protocol is elaborated as follows:(1)
The reader “pings” the tag, detected in its vicinity.(2)
The tag responds with theIDS which acts as an index to locate the data associated with the tag in the database for successful tag identification.(3)
After the tag identification, the reader generates two pseudorandom numbersn1 and n2. The reader then computes and transmits challenge message X=A∥B∥C to the tag.(10)A=IDS⊕K1⊕n1(11)B=IDS∧K2∨n1(12)C=IDS+K3+n2(4)
The tag extractsn1 and n2 from A and C, respectively, and verifies the identity of the reader by calculating a response for message B. After successful reader authentication, the tag calculates and transmits challenge message Y=D∥E.(13)D=IDS∨K4∧n2(14)E=IDS+ID⊕n1The message D is used for the tag authentication whereas the message E is used for the ID communication.(5)
After successful mutual authentication, the dynamic memory on both sides is updated using the following equations:(15)IDSNEW=IDS+n1⊕n2⊕ID(16)K1NEW=K1⊕n2⊕K3+ID(17)K2NEW=K2⊕n2⊕K4+ID(18)K3NEW=K3⊕n1⊕K1+ID(19)K4NEW=K4⊕n1⊕K2+IDThe block diagram of the protocol is given in Figure 3. The cryptanalysis of M2AP was similar to that of LMAP due to similarity in composition of public messages equations and memory architectures.Figure 3
Block diagram of M2AP.


### 2.1.3. Efficient Mutual Authentication Protocol (EMAP)

The EMAP is the third most prominent protocol from the triangular class. The primitives used for the encryption of communication between the tag/reader pair areAND,OR, and XOR. The memory architecture of the tag implementing the EMAP is given in Table 4. The working principle of the protocol is as follows:(1)
The tag receives a “Hello” message from the reader as it enters its communication range.(2)
The reader receives theIDS, which is used for the tag identification by locating the data associated with the communicating tag in the system’s database.(3)
Once the tag is identified, the reader generates the random numbers and sends messageX=A∥B∥C to the tag.(20)A=IDS⊕K1⊕n1(21)B=IDS∨K2⊕n1(22)C=IDS⊕K3⊕n2(4)
The tag extractsn1 from message A and authenticates the reader by calculating the response for challenge message B. After successful reader authentication the tag extracts n2 from the message C, to calculate and send challenge message Y=D∥E.(23)D=IDS∧K4⊕n2(24)E=IDS∧n1∨n2⊕ID⊕K1⊕K2⊕K3⊕K4(5)
The authentication session ends by updating the dynamic memory on both sides.(25)IDSNEW=IDS⊕n2⊕K1(26)K1NEW=K1⊕n2⊕ID1:48∥FpK4∥FpK3(27)K2NEW=K2⊕n2⊕FpK4∥FpK4∥ID49:96(28)K3NEW=K3⊕n1⊕ID1:48∥FpK4∥FpK2(29)K4NEW=K4⊕n1FpK3∥FpK1∥ID49:96The function Fp(x) generates a 24bit version of 96bit input x. The input is divided into twenty-four groups by combining 4bits in each group. The final output is obtained by taking bitwise XOR of all the entities present in each group and concatenating the result. The block diagram of the protocol is given in Figure 4.Figure 4
Block diagram of EMAP.


## 2.1.1. Lightweight Mutual Authentication Protocol (LMAP)

The LMAP laid the foundation of UMAPs and falls under the umbrella of the triangular UMAPs. The memory architecture of the tag and the reader implementing the LMAP is given in Table4. The protocol executes in following steps:(1)
The reader sends the “Hello” message to the tag.(2)
The tag replies withIDS to the reader. This IDS acts as an index in the database to locate the keys and the ID related to the tag. If the required data is not found, the protocol is terminated; otherwise it moves to next step.(3)
In step (3), the reader generates two pseudorandom numbersn1and n2. These random numbers are used for the calculation of the messages A,B and C.(1)A=IDS⊕K1⊕n1(2)B=IDS∨K2⊕n1(3)C=IDS+K2+n2Finally, X=A∥B∥C is transmitted to the tag.(4)
The tag extractsn1 and n2 from the messages A and C, respectively. The message B is a challenge token for the reader authentication. After successful reader authentication, the protocol moves to step (5).(5)
The tag generates and transmits messageD=Y. The message D has two purposes: (a) concealed transfer of the tag’s ID; (b) the tag authentication.(4)D=IDS+ID⊕n1⊕n2After the transmission of the message D, the dynamic variables at the tag’s end are updated using following equations:(5)IDSNEW=IDS+n2⊕K4⊕ID(6)K1NEW=K1⊕n2⊕K3+ID(7)K2NEW=K2⊕n2⊕K4+ID(8)K3NEW=K3⊕n1⊕K1+ID(9)K4NEW=K4⊕n1⊕K2+ID(6)
The reader receives the messageD, authenticates the tag, and updates the dynamic variables using (5)-(9). The process of updating dynamic variables on the reader’s side only takes place in case of successful mutual authentication.Table 4
Memory architecture of triangular UMAPs.
Protocol Storage Location Reader Tag LMAP ( I D , I D S , K 1 , K 2 , K 3 , K 4 ) ( I D , I D S , K 1 , K 2 , K 3 , K 4 ) M2AP EMAPThe flow diagram of the LMAP is given in Figure2. Despite being resource efficient, the LMAP is a weak protocol in terms of structure and equations. The triangular functions alone are unable to conceal the tag’s secrets in public messages due to their imbalance nature. Several cryptanalysis attacks on the LMAP have proved that the protocol cannot be used as a standard for the RFID authentication purposes.Figure 2
Block diagram of LMAP.


## 2.1.2. Minimalistic Mutual Authentication Protocol (M2AP)

The second protocol from the triangular UMAP family is the M2AP. This protocol is similar to the LMAP in terms of the tag’s memory architecture and the protocol’s primitives. The basic difference between the two protocols is the composition of public message Y. The memory architecture of the tag implementing the M2AP is given in Table 4. The step by step execution of the protocol is elaborated as follows:(1)
The reader “pings” the tag, detected in its vicinity.(2)
The tag responds with theIDS which acts as an index to locate the data associated with the tag in the database for successful tag identification.(3)
After the tag identification, the reader generates two pseudorandom numbersn1 and n2. The reader then computes and transmits challenge message X=A∥B∥C to the tag.(10)A=IDS⊕K1⊕n1(11)B=IDS∧K2∨n1(12)C=IDS+K3+n2(4)
The tag extractsn1 and n2 from A and C, respectively, and verifies the identity of the reader by calculating a response for message B. After successful reader authentication, the tag calculates and transmits challenge message Y=D∥E.(13)D=IDS∨K4∧n2(14)E=IDS+ID⊕n1The message D is used for the tag authentication whereas the message E is used for the ID communication.(5)
After successful mutual authentication, the dynamic memory on both sides is updated using the following equations:(15)IDSNEW=IDS+n1⊕n2⊕ID(16)K1NEW=K1⊕n2⊕K3+ID(17)K2NEW=K2⊕n2⊕K4+ID(18)K3NEW=K3⊕n1⊕K1+ID(19)K4NEW=K4⊕n1⊕K2+IDThe block diagram of the protocol is given in Figure 3. The cryptanalysis of M2AP was similar to that of LMAP due to similarity in composition of public messages equations and memory architectures.Figure 3
Block diagram of M2AP.


## 2.1.3. Efficient Mutual Authentication Protocol (EMAP)

The EMAP is the third most prominent protocol from the triangular class. The primitives used for the encryption of communication between the tag/reader pair areAND,OR, and XOR. The memory architecture of the tag implementing the EMAP is given in Table 4. The working principle of the protocol is as follows:(1)
The tag receives a “Hello” message from the reader as it enters its communication range.(2)
The reader receives theIDS, which is used for the tag identification by locating the data associated with the communicating tag in the system’s database.(3)
Once the tag is identified, the reader generates the random numbers and sends messageX=A∥B∥C to the tag.(20)A=IDS⊕K1⊕n1(21)B=IDS∨K2⊕n1(22)C=IDS⊕K3⊕n2(4)
The tag extractsn1 from message A and authenticates the reader by calculating the response for challenge message B. After successful reader authentication the tag extracts n2 from the message C, to calculate and send challenge message Y=D∥E.(23)D=IDS∧K4⊕n2(24)E=IDS∧n1∨n2⊕ID⊕K1⊕K2⊕K3⊕K4(5)
The authentication session ends by updating the dynamic memory on both sides.(25)IDSNEW=IDS⊕n2⊕K1(26)K1NEW=K1⊕n2⊕ID1:48∥FpK4∥FpK3(27)K2NEW=K2⊕n2⊕FpK4∥FpK4∥ID49:96(28)K3NEW=K3⊕n1⊕ID1:48∥FpK4∥FpK2(29)K4NEW=K4⊕n1FpK3∥FpK1∥ID49:96The function Fp(x) generates a 24bit version of 96bit input x. The input is divided into twenty-four groups by combining 4bits in each group. The final output is obtained by taking bitwise XOR of all the entities present in each group and concatenating the result. The block diagram of the protocol is given in Figure 4.Figure 4
Block diagram of EMAP.


## 2.2. UMAP with Single Nontriangular Function

The resource limitation of EPC C1G2 tags confines the computational cost of the UMAPs to4K GE. Initially, the UMAPs only used the triangular functions for the calculation of the challenge/response messages. But triangular protocols were prone to multiple security attacks due to the lack of diffusion in the public messages. The reason behind the inability of encrypted string to conceal the secret values associated with the tag was the imbalance nature of the protocol’s operators.In 2007, Chien [21] introduced the idea of the ultralightweight nontriangular primitive as the protocol’s operator. The use of single nontriangular primitive improved the strength of the UMAPs; however the cryptanalysis of nontriangular UMAPs still highlighted weaknesses in the protocol structure and operators. Some of the prominent UMAPs with single nontriangular primitives are Strong Authentication Strong Integrity (SASI) protocol [21], Gossamer’s protocol [38], and Yeh et al. protocol [39].


### 2.2.1. Strong Authentication Strong Integrity Protocol

The SASI protocol was the first protocol in the field of nontriangular UMAPs. The nontriangular function used in the SASI protocol is the rotation function (Rot(x,y)). The rotation function has two definitions: left rotation of x by the hamming weight of y and left rotation of xbymodofy. For this section, we will consider hamming weight-based rotation function. The memory architecture of the tag implementing the SASI protocol is elaborated in Table 5. The reason behind storing the pair of latest dynamic variables was to provide protection against Denial of Service (DoS) attacks. The working principles of the SASI protocol are as follows:(1)
The reader requests the tag for a pseudoidentification number.(2)
The tag transmits its latestIDS. If the received IDS is found in the database, the protocol proceeds further otherwise the reader requests the tag for the IDS from the previous successful authentication session (IDSold). The successful tag identification leads to the step (3).(3)
The reader generates two random numbersn1 and n2. The dynamic variables and random numbers are used by the reader to generate and transmit X=A∥B∥C.(30)A=IDS⊕K1⊕n1(31)B=IDS∨K2⊕n2(32)K1-=RotK1⊕n2,K1(33)K2-=RotK2⊕n1,K2(34)C=K1⊕K2-+K1-⊕K2(4)
The pseudorandom numbersn1 and n2 are concealed in and communicated to the tag via message A and B, respectively. The message C is used for the reader authentication.(5)
After successful reader authentication, the tag transmits messageY=D for the tag authentication and the ID transmission.(35)D=K2-+ID⊕K1⊕K2∨K1-(6)
After mutual authentication, the dynamic variables on both sides are updated using following equations:(36)IDSold=IDS,K1old=K1,K2old=K2(37)IDS=IDSold+ID⊕n2⊕K1-,K1=K1-,K2=K2-The flowchart of the SASI protocol is given in Figure 5.Table 5
Memory architectures of UMAPs with single nontriangular function.
Protocol Storage Location Reader Tag SASI ( I D , I D S , K 1 , K 2 ) ( I D , I D S , K 1 , K 2 , I D S o l d , K 1 o l d , K 2 o l d ) Gossamer’s Protocol ( I D , I D S , K 1 , K 2 ) ( I D , I D S , K 1 , K 2 , I D S o l d , K 1 o l d , K 2 o l d ) Yeh et al.’s Protocol ( I D , I D S , I D S o l d , K , K o l d ) ( I D , I D S , K )Figure 5
Block diagram of SASI protocol.


### 2.2.2. Gossamer’s Protocol

In 2008, Peris-Lopez presented nontriangular UMAPs to overcome the weaknesses of the SASI protocol. In the Gossamer’s protocol, the memory architecture of the system was enhanced by saving the latest copy of dynamic variables on the tag’s side. The memory architecture of the protocol is given in Table5. The nontriangular primitive of the Gossamer’s protocol is mix bit function (mixbit(a,b)). The mix bit function consists of two subfunction: the rotation and the modular addition function. These subfunctions are used independently and in collaborative manner to calculate the challenge/response messages. The working principle of x=mixbit(a,b) is elaborated in Figure 7.The protocol executes in five steps which are defined as follows:(1)
The reader sends a request for theIDS to the tag present in its vicinity.(2)
The reader tries to locate the tags information by searching the database with the help of the receivedIDS. The tag is identified if its information is found in the database.(3)
The reader generates pseudorandom private keysn1 and n2. The reader then sends message X=A∥B∥C to the tag.(38)A=RotRotIDS+K1+π+n1,K2+K1,K1(39)B=RotRotIDS+K2+π+n2,K1+K2,K2(40)n3=Mixbitn1,n2(41)K1∗=RotRotn2+K1+π+n3,n2+K2⊕n3,n1⊕n3(42)K2∗=RotRotn1+K2+π+n3,n1+K1+n3,n2+n3(43)n1′=Mixbitn3,n2(44)C=RotRotn3+K1∗+π+n1′,n3+K2∗⊕n1′,n2⊕n1′(4)
The reader is authenticated by generating a response to the messageC. After that, the tag calculates and transmits the challenge message Y=D.(45)D=RotRotn2+K2∗+ID+n1′,n2+K1∗+n1′,n3+n1(5)
The dynamic variable on both sides are updated after a successful mutual authentication.(46)IDSold=IDS;K1old=K1;K2old=K2(47)n2′=Mixbitn1′,n3(48)IDS=RotRotn1′+K1∗+IDS+n2′,n1′+K2∗⊕n2′,n3⊕n2′(49)K1=RotRotn3+K2∗+π+n2′,n3+K1∗+n2′,n1′+n2′(50)K2=RotRotIDSnew+K2∗+π+K1new,IDSnew+K1∗+K1new,n2′+K1newThe constantπ used in the protocol assumes the value 0x3243F6A8885A308D313198A2. The block diagram of the Gossamer’s protocol is presented in Figure 6.Figure 6
Block diagram of Gossamer’s protocol.Figure 7
m i x b i t ( a , b ) algorithm.


### 2.2.3. Yeh et al. Protocol

In 2010, Yeh et al. [39] proposed a process oriented UMAP. The feature that differentiates this protocol from its predecessors is the DoS avoidance mechanism. In this protocol, the pairs of latest dynamic variables are stored at the reader side instead of the tag. The reader also maintains a flag to identify whether the tag/reader pair is fully synchronized or not. The nontriangular function used in the protocol is the rotation function (Rot(a,b)). The memory architecture of the UMAP is given in Table 5. The working principle of the Yeh et al. protocol is as follows: the protocol is the rotation function (Rot(a,b)). The memory architecture of the UMAP is as follows:(1)
The reader initiates the communication by sending a “Hello” message to the tag.(2)
As a response, the tag transmits theIDS stored in its dynamic memory.(3)
After successful tag identification through the database, the reader generates two pseudorandom numbersn1 and n2. If the IDS=IDSnew, the reader sets an internal flag f=0; otherwise the flag’s value sets to 1, the key K updates and becomes equal to the tag’s ID. After key updation, the reader calculates and sends message X=A∥B∥C∥f to the tag.(51)A=IDS⊕K⊕n1(52)B=IDS∨K⊕n2(53)K∗=RotK⊕n2,n1(54)C=K∗⊕n1+n2(55)f=flagbit;f=0ifIDS=IDSNEWf=1ifIDS=IDSOLD(4)
Upon receiving the challenge message, the tag updates the value of the keyK based on the flag status. After that n1 and n2 are extracted and the reader is authenticated.(5)
The successful reader verification leads to the calculation and transmission of the tag authentication challenge messageD.(56)K¨∗=RotK⊕n1,n2(57)D=K¨∗⊕n2+n1(6)
In case of successful mutual authentication, the dynamic memory on both sides is updated.(58)IDSNew=IDS+ID⊕K¨∗⊕n1⊕n2(59)KNew=K∗The block diagram of the Yeh et al. protocol is given in Figure8.Figure 8
Block diagram of Yeh et al. protocol.


## 2.2.1. Strong Authentication Strong Integrity Protocol

The SASI protocol was the first protocol in the field of nontriangular UMAPs. The nontriangular function used in the SASI protocol is the rotation function (Rot(x,y)). The rotation function has two definitions: left rotation of x by the hamming weight of y and left rotation of xbymodofy. For this section, we will consider hamming weight-based rotation function. The memory architecture of the tag implementing the SASI protocol is elaborated in Table 5. The reason behind storing the pair of latest dynamic variables was to provide protection against Denial of Service (DoS) attacks. The working principles of the SASI protocol are as follows:(1)
The reader requests the tag for a pseudoidentification number.(2)
The tag transmits its latestIDS. If the received IDS is found in the database, the protocol proceeds further otherwise the reader requests the tag for the IDS from the previous successful authentication session (IDSold). The successful tag identification leads to the step (3).(3)
The reader generates two random numbersn1 and n2. The dynamic variables and random numbers are used by the reader to generate and transmit X=A∥B∥C.(30)A=IDS⊕K1⊕n1(31)B=IDS∨K2⊕n2(32)K1-=RotK1⊕n2,K1(33)K2-=RotK2⊕n1,K2(34)C=K1⊕K2-+K1-⊕K2(4)
The pseudorandom numbersn1 and n2 are concealed in and communicated to the tag via message A and B, respectively. The message C is used for the reader authentication.(5)
After successful reader authentication, the tag transmits messageY=D for the tag authentication and the ID transmission.(35)D=K2-+ID⊕K1⊕K2∨K1-(6)
After mutual authentication, the dynamic variables on both sides are updated using following equations:(36)IDSold=IDS,K1old=K1,K2old=K2(37)IDS=IDSold+ID⊕n2⊕K1-,K1=K1-,K2=K2-The flowchart of the SASI protocol is given in Figure 5.Table 5
Memory architectures of UMAPs with single nontriangular function.
Protocol Storage Location Reader Tag SASI ( I D , I D S , K 1 , K 2 ) ( I D , I D S , K 1 , K 2 , I D S o l d , K 1 o l d , K 2 o l d ) Gossamer’s Protocol ( I D , I D S , K 1 , K 2 ) ( I D , I D S , K 1 , K 2 , I D S o l d , K 1 o l d , K 2 o l d ) Yeh et al.’s Protocol ( I D , I D S , I D S o l d , K , K o l d ) ( I D , I D S , K )Figure 5
Block diagram of SASI protocol.


## 2.2.2. Gossamer’s Protocol

In 2008, Peris-Lopez presented nontriangular UMAPs to overcome the weaknesses of the SASI protocol. In the Gossamer’s protocol, the memory architecture of the system was enhanced by saving the latest copy of dynamic variables on the tag’s side. The memory architecture of the protocol is given in Table5. The nontriangular primitive of the Gossamer’s protocol is mix bit function (mixbit(a,b)). The mix bit function consists of two subfunction: the rotation and the modular addition function. These subfunctions are used independently and in collaborative manner to calculate the challenge/response messages. The working principle of x=mixbit(a,b) is elaborated in Figure 7.The protocol executes in five steps which are defined as follows:(1)
The reader sends a request for theIDS to the tag present in its vicinity.(2)
The reader tries to locate the tags information by searching the database with the help of the receivedIDS. The tag is identified if its information is found in the database.(3)
The reader generates pseudorandom private keysn1 and n2. The reader then sends message X=A∥B∥C to the tag.(38)A=RotRotIDS+K1+π+n1,K2+K1,K1(39)B=RotRotIDS+K2+π+n2,K1+K2,K2(40)n3=Mixbitn1,n2(41)K1∗=RotRotn2+K1+π+n3,n2+K2⊕n3,n1⊕n3(42)K2∗=RotRotn1+K2+π+n3,n1+K1+n3,n2+n3(43)n1′=Mixbitn3,n2(44)C=RotRotn3+K1∗+π+n1′,n3+K2∗⊕n1′,n2⊕n1′(4)
The reader is authenticated by generating a response to the messageC. After that, the tag calculates and transmits the challenge message Y=D.(45)D=RotRotn2+K2∗+ID+n1′,n2+K1∗+n1′,n3+n1(5)
The dynamic variable on both sides are updated after a successful mutual authentication.(46)IDSold=IDS;K1old=K1;K2old=K2(47)n2′=Mixbitn1′,n3(48)IDS=RotRotn1′+K1∗+IDS+n2′,n1′+K2∗⊕n2′,n3⊕n2′(49)K1=RotRotn3+K2∗+π+n2′,n3+K1∗+n2′,n1′+n2′(50)K2=RotRotIDSnew+K2∗+π+K1new,IDSnew+K1∗+K1new,n2′+K1newThe constantπ used in the protocol assumes the value 0x3243F6A8885A308D313198A2. The block diagram of the Gossamer’s protocol is presented in Figure 6.Figure 6
Block diagram of Gossamer’s protocol.Figure 7
m i x b i t ( a , b ) algorithm.


## 2.2.3. Yeh et al. Protocol

In 2010, Yeh et al. [39] proposed a process oriented UMAP. The feature that differentiates this protocol from its predecessors is the DoS avoidance mechanism. In this protocol, the pairs of latest dynamic variables are stored at the reader side instead of the tag. The reader also maintains a flag to identify whether the tag/reader pair is fully synchronized or not. The nontriangular function used in the protocol is the rotation function (Rot(a,b)). The memory architecture of the UMAP is given in Table 5. The working principle of the Yeh et al. protocol is as follows: the protocol is the rotation function (Rot(a,b)). The memory architecture of the UMAP is as follows:(1)
The reader initiates the communication by sending a “Hello” message to the tag.(2)
As a response, the tag transmits theIDS stored in its dynamic memory.(3)
After successful tag identification through the database, the reader generates two pseudorandom numbersn1 and n2. If the IDS=IDSnew, the reader sets an internal flag f=0; otherwise the flag’s value sets to 1, the key K updates and becomes equal to the tag’s ID. After key updation, the reader calculates and sends message X=A∥B∥C∥f to the tag.(51)A=IDS⊕K⊕n1(52)B=IDS∨K⊕n2(53)K∗=RotK⊕n2,n1(54)C=K∗⊕n1+n2(55)f=flagbit;f=0ifIDS=IDSNEWf=1ifIDS=IDSOLD(4)
Upon receiving the challenge message, the tag updates the value of the keyK based on the flag status. After that n1 and n2 are extracted and the reader is authenticated.(5)
The successful reader verification leads to the calculation and transmission of the tag authentication challenge messageD.(56)K¨∗=RotK⊕n1,n2(57)D=K¨∗⊕n2+n1(6)
In case of successful mutual authentication, the dynamic memory on both sides is updated.(58)IDSNew=IDS+ID⊕K¨∗⊕n1⊕n2(59)KNew=K∗The block diagram of the Yeh et al. protocol is given in Figure8.Figure 8
Block diagram of Yeh et al. protocol.


## 2.3. UMAPs with Hybrid Nontriangular Function

The cryptanalysis of the UMAPs with single nontriangular functions proved the inability of the protocols to provide Confidentiality, Integrity, Availability and Authentication (CIAA) to the communicating parties. In order to further improve the security, the concept of using hybrid nontriangular functions was introduced. This idea improved the security and privacy services offered by the UMAPs. There are many hybrid nontriangular UMAPs available in the literature. In this subsection, the protocols under consideration are RFID Authentication Protocol with Permutation (RAPP) [4], RFID Authentication Protocol for Low cost Tags (RAPLT) [40], Robust Confidentiality Integrity and Authentication (RCIA) protocol [41], and Succinct and Lightweight Authentication Protocol (SLAP) [30].


### 2.3.1. RFID Authentication Protocol with Permutation (RAPP)

The RAPP protocol was different from previously presented UMAPs, in terms of the primitives used for encryption and the sequence of interaction between the tag and the reader. The protocol only used three operations, i.e.,XOR, rotation (Rot(x,y)) and permutation (Per(x,y)).TheRot(x,y) corresponds to the left rotation of x by the hamming weight of y. The description of permutation function (z=per(x,y)) is as follows. Let z be a L-bit word and zi be the ith bit of z where 1≤i≤L, and z1 and zL be the LSB and MSB of the word z, respectively. Suppose x and y are two L-bit words and hamming weight of y is m. Moreover yi=1 if i∈I1={km,km-1…k1} and yi=0 if i∈I0={kL,kL-1…km+1}.(60)km>km-1>⋯>k1kL>kL-1>⋯>km+1The permutation ofx according to y, i.e., per(x,y) is equal to(61)Perx,y=xkm,xkm-1…xk1,xkL,xkL-1…xkm+1Unlike conventional sequence of interaction, the dynamic memory of the tag is updated after getting a confirmation message of successful mutual authentication of the tag/reader pair. The aim of this message was to make the protocol resistant to the desynchronization attacks. The memory architecture of the protocol is given in Table6 and the detail description of the protocol is as follows:(1)
The tag receives a “Hello” message from the reader as soon as it enters its vicinity.(2)
The tag responds with the value ofIDS stored in its dynamic memory. The reader identifies the tag by retrieving the information indexed by the IDS value in the database.(3)
After successful tag identification, the reader generates a random numbern1 and sends challenge message X=A∥B to the tag.(62)A=PerK2,K1⊕n1(63)B=PerK1⊕K2,Rotn1,n2⊕Pern1,K1(4)
The tag verifies the reader’s identity and sends the challenge messageY=C to the reader.(64)C=Pern1⊕K1,n1⊕K3⊕ID(5)
In case of successful mutual authentication, the reader updates the dynamic variables, generates another random numbern2, and sends the mutual authentication verification message D∥E to the tag.(65)D=PerK3,K2⊕n2(66)E=PerK3,Rotn2,n2⊕Pern1,K3⊕K2(6)
The tag updates its dynamic memory after verifying the origin of messageD∥E.(67)IDSNew=PerIDS,n1⊕n2⊕K1⊕K2⊕K3(68)K1New=PerK1,n1⊕K2(69)K2New=PerK2,n2⊕K1(70)K3New=PerK3,n1⊕n2⊕IDSTable 6
Memory architecture of UMAPs with hybrid nontriangular functions.
Protocol Storage Location Reader Tag RAPP ( I D , I D S , K 1 , K 2 , K 3 , I D S o l d , K 1 o l d , K 2 o l d , K 3 o l d ) ( I D , I D S , K 1 , K 2 , K 3 ) RAPLT ( I D , I D S , K 1 , K 2 , I D S o l d ) ( I D , I D S , K 1 , K 2 , I D S o l d ) RCIA ( I D , I D S , K 1 , K 2 , I D S o l d , K 1 o l d , K 2 o l d ) ( I D , I D S , K 1 , K 2 , I D S o l d , K 1 o l d , K 2 o l d ) SLAP I D , I D S N E W , K 1 N E W , K 2 N E W , I D S O L D , K 1 O L D , K 2 O L D I D , I D S N E W , K 1 N E W , K 2 N E W , I D S O L D , K 1 O L D , K 2 O L DThe block diagram of the protocol is given in Figure9.Figure 9
Block diagram of RAPP protocol.


### 2.3.2. RFID Authentication Protocol for Low Cost Tags (RAPLT)

In 2013, Jeon and Yoon improved the permutation function and proposed two new nontriangular function, i.e., Merge(Mer(a,b,c,d)) and separate (Sep(d,c,b,,a)) operations in RFID Authentication Protocol for Low cost Tags (RAPLT). These operations are considered to be more reliable and secure compared to the permutation function.Assumea and b are L bit numbers whereas c and d are 2L bit strings. The formation of a,b,c,d and pseudocode for Mer(a,b,c,d) and Sep(d,c,b,,a) operations are given in Figure 10.Figure 10
Merge and separate operate.Both operations have inverse relation and are extremely lightweight in nature. In RAPLT protocol, both the tag and the reader stores a pair of the latestIDS, the latest keys and the tag’s ID. The working principle of the RAPLT protocol is as follows:(1)
The reader initiates the protocol by sending a “Hello” message to the tag.(2)
As a response, the tag sends the index pseudonym(IDS) for the tag identification.(3)
After the successful tag identification throughIDS, the reader generates two random numbers (n1,n2) and computes X=A1∥A2∥B3.(71)N1=n1⊕ID;N2=n2⊕IDS(72)MerN1,N2·K1∥K2,A1∥A2(73)M1=ID⊕n1⊕K2;M2=IDS⊕n2⊕K1(74)SepM1,M2·K1∥K2,B1∥B2(75)B3=B1⊕B2(4)
The tag authenticates the reader by generating a response for the messageB3. A successful reader verification leads to the calculation and transmission of Y=C3.(76)MerK1,K2,K1∥K2,K′1∥K′2(77)Mern2,N1,K′1∥K′2,C1∥C2(78)C3=C1⊕C2(5)
The tag authentication is followed by theIDS update on both sides.(79)IDSNEW=n1The flow diagram of the RAPLT protocol is given in Figure11.Figure 11
Block diagram of RAPLT.


### 2.3.3. Robust Confidentiality Integrity and Authentication Protocol (RCIA)

The Robust Confidentiality Integrity and Authentication (RCIA) protocol is designed on the theme of the RAPP protocol. This protocol is associated with hybrid category of the UMAPs as it uses two nontriangular functions, i.e., rotation(Rot(x,y)) and recursive hash (Rh(x)). The working principle of the recursive hash (Rh(x)) functions consists of following steps:(i)
Considerx as an L bit string and decimate the input x into k chunks with equal numbers of bits per chunk. (#ofbitsperchunk=L/k).(ii)
Assume a seed values from the range [0,k-1].(iii)
The seeds calculated in above step selects the corresponding memory block (ks) of the decimated string x.(iv)
Final answer of recursive hash function is obtained by concatenating the results of following operations.
(a)
TakeXOR between the selected memory block ks and all the other blocks except the block itself.(b)
Left rotate the blockks by the hamming weight of itself (Rotks,ks).For efficient hardware implementation, the96bit input of the recursive hash function is decimated into k=12 chunks, each containing 8bits. Both the tag and the reader store seven Lbits strings associated with the tag. These numbers are ID,(IDS,K1,K2) and (IDSold,K1old,K2old). The RCIA protocol executes in five steps which are as follows:(1)
The reader sends a “Hello” message to the tag.(2)
The tag sendsIDS to the reader. If the value is found in the database, the protocol proceeds otherwise the reader requests for IDSold and matches it with the database value. The protocol proceeds to the next step only when the received IDS is found in the database.(3)
The reader generates random numbersn1 and n2. It also calculates R=n1⊕n2. This value is used to find the seed value. The equation for seed calculation is s=Rmod⁡k. The calculation of seed value leads to calculation and transmission of X=A∥B∥C messages.(80)A=RotIDS,K1⊕n1(81)B=RotIDS∧n1,K2∧K1⊕n2(82)R=n1⊕n2;s=Rmod⁡k(83)K1∗=RotRhK2,Rhn1∧K1(84)K2∗=RotRhK1,Rhn2∧K2(85)C=RotRhK1∗,RhK2∗∧RotRhn1,Rhn2(4)
The messageC is used for the reader authentication. After one sided successful authentication, the tag updates its dynamic variables and sends the message D.(86)D=RotRhID,K1∗∧RotRhK2∗,Rhn2⊕IDS(5)
The reader uses the stringD for the tag authentication after which the dynamic variables also updates on the reader’s side. The update equations are as follows:(87)IDSNEW=RotRhIDS⊕n2,n1(88)K1NEW=K1∗;K2NEW=K2∗Figure12 shows the block diagram of the RCIA protocol.Figure 12
Block diagram of RCIA protocol.


### 2.3.4. Succinct and Lightweight Authentication Protocol (SLAP)

In 2016, an ultralightweight authentication protocol named Succinct and Lightweight Authentication Protocol (SLAP) was proposed. The SLAP algorithm is composed of three operators, i.e.,XOR, rotation (Rot(a,b)), and Conversion (Conv(a,b)) function. These functions are lightweight with respect to the implementation cost and are appropriate for the passive electronic chips. The conversion function is the main feature of the protocol that guarantees irreversibility, confidentiality, full confusion, and low complexity.The conversion function(Conv(a,b)) consists of three subfunctions. Suppose the size of input strings (a,b) is L bits, i.e., (89)a=aLaL-1aL-2…a1;b=bLbL-1bL-2…b1The description of these functions is as follows:(i)
Grouping. The inputs a and b are divided into segments based on the hamming weight and a threshold t. Consider the input a; based on the hamming weight m=Hw(a) divide the input string into two parts, i.e., (a1=aLaL-1…am+1) and (a2=amam-1…a1). Continue the segmentation process based on hamming weight until the smallest segment size becomes equal to the threshold value t. The input string b is also segmented based on n=hw(b) and the threshold t. The respective segments are concatenated to form the output (a′,b′) of grouping function.(ii)
Rearrange. In this step, the regrouping of a′ and b′ bits takes place. As the length of input strings is same, exchanging the grouping form between of a′ and b′ gives two L-bit numbers. Finally, each subgroup is left rotated by its hamming weight. The output of rearrange function (a′′,b′′) is the shuffled version of a and b.(iii)
Composition. The final output of conversion function is obtained by taking XOR of the shuffled version of a and b, i.e., c=a′′⊕b′′.The RFID system implementing the SLAP stores the latest pair of dynamic variables on both communicating ends. The working principle of the protocol is as follows:(1)
The tag receives a “hello” message from the reader after entering its vicinity.(2)
The tag responds with its identity pseudonymIDS. This value is used for the tag identification at the reader’s side.(3)
After successful identification, the reader generates a random numbern and conceal it in the message A. The reader also generates a challenge message B. The reader transmits message A along with left or right half of B based on Hw(B). If Hw(B)=odd, X=A∥Bl; otherwise X=A∥Br.(90)A=ConvK1,K2⊕n(91)B=ConvRotK1,n,K1⊕K2⊕RotConvK2,K2⊕n,K1(4)
The tag authenticates the reader by generating a response to messageB. After successful reader authentication, the tag calculates the message C and transmits the left or right half of C based on Hw(C). If Hw(C)=odd, Y=Cl; otherwise Y=Cr.(92)C=ConvConvB,K1NEW,ConvK1NEW,K2NEW⊕n⊕ID(5)
After identity verification, the dynamic variables of each side are updated using following equation:(93)IDSNEW=ConvIDS,n⊕BLorR∥CLorR(94)K1NEW=ConvK1,n⊕K2;K2NEW=ConvK2,n⊕K1The block diagram of the SLAP is given in Figure13.Figure 13
Block diagram of SLAP.A brief survey on the existing protocols proves that increase in computational complexity of the authentication mechanism improves the CIAA capabilities of the protocol at the cost of increased gate equivalents. Section3 presents a set of eminent cryptanalysis models that are being used to evaluate the security and the privacy features of the UMAPs. The literature review shows that almost all the existing UMAPs have been subjected to multiple cryptanalysis attacks. The unavailability of secure and reliable UMAP for RFID enabled IoT networks is one of the major challenges in the standardization of the secure architecture for the resource constraint IoT network perception layer. The subsequent sections present a comprehensive security analysis model to evaluate the strengths of the RFID node authentication protocols, the CIAA analysis of the existing UMAPs based on the presented model, and a secure and reliable UMAP termed as Extremely Good Privacy (EGP) protocol for the authentication of resource constraint IoT nodes.


## 2.3.1. RFID Authentication Protocol with Permutation (RAPP)

The RAPP protocol was different from previously presented UMAPs, in terms of the primitives used for encryption and the sequence of interaction between the tag and the reader. The protocol only used three operations, i.e.,XOR, rotation (Rot(x,y)) and permutation (Per(x,y)).TheRot(x,y) corresponds to the left rotation of x by the hamming weight of y. The description of permutation function (z=per(x,y)) is as follows. Let z be a L-bit word and zi be the ith bit of z where 1≤i≤L, and z1 and zL be the LSB and MSB of the word z, respectively. Suppose x and y are two L-bit words and hamming weight of y is m. Moreover yi=1 if i∈I1={km,km-1…k1} and yi=0 if i∈I0={kL,kL-1…km+1}.(60)km>km-1>⋯>k1kL>kL-1>⋯>km+1The permutation ofx according to y, i.e., per(x,y) is equal to(61)Perx,y=xkm,xkm-1…xk1,xkL,xkL-1…xkm+1Unlike conventional sequence of interaction, the dynamic memory of the tag is updated after getting a confirmation message of successful mutual authentication of the tag/reader pair. The aim of this message was to make the protocol resistant to the desynchronization attacks. The memory architecture of the protocol is given in Table6 and the detail description of the protocol is as follows:(1)
The tag receives a “Hello” message from the reader as soon as it enters its vicinity.(2)
The tag responds with the value ofIDS stored in its dynamic memory. The reader identifies the tag by retrieving the information indexed by the IDS value in the database.(3)
After successful tag identification, the reader generates a random numbern1 and sends challenge message X=A∥B to the tag.(62)A=PerK2,K1⊕n1(63)B=PerK1⊕K2,Rotn1,n2⊕Pern1,K1(4)
The tag verifies the reader’s identity and sends the challenge messageY=C to the reader.(64)C=Pern1⊕K1,n1⊕K3⊕ID(5)
In case of successful mutual authentication, the reader updates the dynamic variables, generates another random numbern2, and sends the mutual authentication verification message D∥E to the tag.(65)D=PerK3,K2⊕n2(66)E=PerK3,Rotn2,n2⊕Pern1,K3⊕K2(6)
The tag updates its dynamic memory after verifying the origin of messageD∥E.(67)IDSNew=PerIDS,n1⊕n2⊕K1⊕K2⊕K3(68)K1New=PerK1,n1⊕K2(69)K2New=PerK2,n2⊕K1(70)K3New=PerK3,n1⊕n2⊕IDSTable 6
Memory architecture of UMAPs with hybrid nontriangular functions.
Protocol Storage Location Reader Tag RAPP ( I D , I D S , K 1 , K 2 , K 3 , I D S o l d , K 1 o l d , K 2 o l d , K 3 o l d ) ( I D , I D S , K 1 , K 2 , K 3 ) RAPLT ( I D , I D S , K 1 , K 2 , I D S o l d ) ( I D , I D S , K 1 , K 2 , I D S o l d ) RCIA ( I D , I D S , K 1 , K 2 , I D S o l d , K 1 o l d , K 2 o l d ) ( I D , I D S , K 1 , K 2 , I D S o l d , K 1 o l d , K 2 o l d ) SLAP I D , I D S N E W , K 1 N E W , K 2 N E W , I D S O L D , K 1 O L D , K 2 O L D I D , I D S N E W , K 1 N E W , K 2 N E W , I D S O L D , K 1 O L D , K 2 O L DThe block diagram of the protocol is given in Figure9.Figure 9
Block diagram of RAPP protocol.


## 2.3.2. RFID Authentication Protocol for Low Cost Tags (RAPLT)

In 2013, Jeon and Yoon improved the permutation function and proposed two new nontriangular function, i.e., Merge(Mer(a,b,c,d)) and separate (Sep(d,c,b,,a)) operations in RFID Authentication Protocol for Low cost Tags (RAPLT). These operations are considered to be more reliable and secure compared to the permutation function.Assumea and b are L bit numbers whereas c and d are 2L bit strings. The formation of a,b,c,d and pseudocode for Mer(a,b,c,d) and Sep(d,c,b,,a) operations are given in Figure 10.Figure 10
Merge and separate operate.Both operations have inverse relation and are extremely lightweight in nature. In RAPLT protocol, both the tag and the reader stores a pair of the latestIDS, the latest keys and the tag’s ID. The working principle of the RAPLT protocol is as follows:(1)
The reader initiates the protocol by sending a “Hello” message to the tag.(2)
As a response, the tag sends the index pseudonym(IDS) for the tag identification.(3)
After the successful tag identification throughIDS, the reader generates two random numbers (n1,n2) and computes X=A1∥A2∥B3.(71)N1=n1⊕ID;N2=n2⊕IDS(72)MerN1,N2·K1∥K2,A1∥A2(73)M1=ID⊕n1⊕K2;M2=IDS⊕n2⊕K1(74)SepM1,M2·K1∥K2,B1∥B2(75)B3=B1⊕B2(4)
The tag authenticates the reader by generating a response for the messageB3. A successful reader verification leads to the calculation and transmission of Y=C3.(76)MerK1,K2,K1∥K2,K′1∥K′2(77)Mern2,N1,K′1∥K′2,C1∥C2(78)C3=C1⊕C2(5)
The tag authentication is followed by theIDS update on both sides.(79)IDSNEW=n1The flow diagram of the RAPLT protocol is given in Figure11.Figure 11
Block diagram of RAPLT.


## 2.3.3. Robust Confidentiality Integrity and Authentication Protocol (RCIA)

The Robust Confidentiality Integrity and Authentication (RCIA) protocol is designed on the theme of the RAPP protocol. This protocol is associated with hybrid category of the UMAPs as it uses two nontriangular functions, i.e., rotation(Rot(x,y)) and recursive hash (Rh(x)). The working principle of the recursive hash (Rh(x)) functions consists of following steps:(i)
Considerx as an L bit string and decimate the input x into k chunks with equal numbers of bits per chunk. (#ofbitsperchunk=L/k).(ii)
Assume a seed values from the range [0,k-1].(iii)
The seeds calculated in above step selects the corresponding memory block (ks) of the decimated string x.(iv)
Final answer of recursive hash function is obtained by concatenating the results of following operations.
(a)
TakeXOR between the selected memory block ks and all the other blocks except the block itself.(b)
Left rotate the blockks by the hamming weight of itself (Rotks,ks).For efficient hardware implementation, the96bit input of the recursive hash function is decimated into k=12 chunks, each containing 8bits. Both the tag and the reader store seven Lbits strings associated with the tag. These numbers are ID,(IDS,K1,K2) and (IDSold,K1old,K2old). The RCIA protocol executes in five steps which are as follows:(1)
The reader sends a “Hello” message to the tag.(2)
The tag sendsIDS to the reader. If the value is found in the database, the protocol proceeds otherwise the reader requests for IDSold and matches it with the database value. The protocol proceeds to the next step only when the received IDS is found in the database.(3)
The reader generates random numbersn1 and n2. It also calculates R=n1⊕n2. This value is used to find the seed value. The equation for seed calculation is s=Rmod⁡k. The calculation of seed value leads to calculation and transmission of X=A∥B∥C messages.(80)A=RotIDS,K1⊕n1(81)B=RotIDS∧n1,K2∧K1⊕n2(82)R=n1⊕n2;s=Rmod⁡k(83)K1∗=RotRhK2,Rhn1∧K1(84)K2∗=RotRhK1,Rhn2∧K2(85)C=RotRhK1∗,RhK2∗∧RotRhn1,Rhn2(4)
The messageC is used for the reader authentication. After one sided successful authentication, the tag updates its dynamic variables and sends the message D.(86)D=RotRhID,K1∗∧RotRhK2∗,Rhn2⊕IDS(5)
The reader uses the stringD for the tag authentication after which the dynamic variables also updates on the reader’s side. The update equations are as follows:(87)IDSNEW=RotRhIDS⊕n2,n1(88)K1NEW=K1∗;K2NEW=K2∗Figure12 shows the block diagram of the RCIA protocol.Figure 12
Block diagram of RCIA protocol.


## 2.3.4. Succinct and Lightweight Authentication Protocol (SLAP)

In 2016, an ultralightweight authentication protocol named Succinct and Lightweight Authentication Protocol (SLAP) was proposed. The SLAP algorithm is composed of three operators, i.e.,XOR, rotation (Rot(a,b)), and Conversion (Conv(a,b)) function. These functions are lightweight with respect to the implementation cost and are appropriate for the passive electronic chips. The conversion function is the main feature of the protocol that guarantees irreversibility, confidentiality, full confusion, and low complexity.The conversion function(Conv(a,b)) consists of three subfunctions. Suppose the size of input strings (a,b) is L bits, i.e., (89)a=aLaL-1aL-2…a1;b=bLbL-1bL-2…b1The description of these functions is as follows:(i)
Grouping. The inputs a and b are divided into segments based on the hamming weight and a threshold t. Consider the input a; based on the hamming weight m=Hw(a) divide the input string into two parts, i.e., (a1=aLaL-1…am+1) and (a2=amam-1…a1). Continue the segmentation process based on hamming weight until the smallest segment size becomes equal to the threshold value t. The input string b is also segmented based on n=hw(b) and the threshold t. The respective segments are concatenated to form the output (a′,b′) of grouping function.(ii)
Rearrange. In this step, the regrouping of a′ and b′ bits takes place. As the length of input strings is same, exchanging the grouping form between of a′ and b′ gives two L-bit numbers. Finally, each subgroup is left rotated by its hamming weight. The output of rearrange function (a′′,b′′) is the shuffled version of a and b.(iii)
Composition. The final output of conversion function is obtained by taking XOR of the shuffled version of a and b, i.e., c=a′′⊕b′′.The RFID system implementing the SLAP stores the latest pair of dynamic variables on both communicating ends. The working principle of the protocol is as follows:(1)
The tag receives a “hello” message from the reader after entering its vicinity.(2)
The tag responds with its identity pseudonymIDS. This value is used for the tag identification at the reader’s side.(3)
After successful identification, the reader generates a random numbern and conceal it in the message A. The reader also generates a challenge message B. The reader transmits message A along with left or right half of B based on Hw(B). If Hw(B)=odd, X=A∥Bl; otherwise X=A∥Br.(90)A=ConvK1,K2⊕n(91)B=ConvRotK1,n,K1⊕K2⊕RotConvK2,K2⊕n,K1(4)
The tag authenticates the reader by generating a response to messageB. After successful reader authentication, the tag calculates the message C and transmits the left or right half of C based on Hw(C). If Hw(C)=odd, Y=Cl; otherwise Y=Cr.(92)C=ConvConvB,K1NEW,ConvK1NEW,K2NEW⊕n⊕ID(5)
After identity verification, the dynamic variables of each side are updated using following equation:(93)IDSNEW=ConvIDS,n⊕BLorR∥CLorR(94)K1NEW=ConvK1,n⊕K2;K2NEW=ConvK2,n⊕K1The block diagram of the SLAP is given in Figure13.Figure 13
Block diagram of SLAP.A brief survey on the existing protocols proves that increase in computational complexity of the authentication mechanism improves the CIAA capabilities of the protocol at the cost of increased gate equivalents. Section3 presents a set of eminent cryptanalysis models that are being used to evaluate the security and the privacy features of the UMAPs. The literature review shows that almost all the existing UMAPs have been subjected to multiple cryptanalysis attacks. The unavailability of secure and reliable UMAP for RFID enabled IoT networks is one of the major challenges in the standardization of the secure architecture for the resource constraint IoT network perception layer. The subsequent sections present a comprehensive security analysis model to evaluate the strengths of the RFID node authentication protocols, the CIAA analysis of the existing UMAPs based on the presented model, and a secure and reliable UMAP termed as Extremely Good Privacy (EGP) protocol for the authentication of resource constraint IoT nodes.


## 3. Cryptanalysis Models for UMAPs

Since 2006, numerous UMAPs have been proposed for the EPC C1G2 identification system. However, most of these protocols were very weak and were found to be vulnerable within one year of their introduction [19, 42, 43]. The reason behind this hasty failure was lack of compact security analysis of the protocol at the design stage.A comprehensive security analysis should perform the formal analysis of a protocol and the strength evaluation against at least three basic cryptanalysis models: desynchronization, traceability, and full disclosure attacks. This section provides a brief description of the above stated security analysis model along with the cryptanalysis of UMAPs defined in previous section, to highlight the need of secure and reliable authentication protocol for RFID based IoT networks.


### 3.1. Formal Analysis

The formal analysis is performed to evaluate the protocol’s ability to authenticate the communicating entities under multiple channel conditions. The sequence of challenge/response message exchange between the tag and the reader is examined by virtue of following methods.


#### 3.1.1. Logic of Belief Analysis

This method analyzes the public message composition and sequence of interaction between the communicating parties to systematically evaluate the protocol’s functionality on an abstract level. The objectives of logic of belief analysis are as follows:(i)
State what is accomplished by the protocol(ii)
Draw attention to unnecessary actions that can be removed from a protocol(iii)
Highlight any encrypted messages that could be sent in clear textThe prominent mathematical models used for the logic of belief analysis are Burrows–Abadi–Needham (BAN) logic model and Gong–Needham–Yahalom (GNY) logic model.


#### 3.1.2. Automated Security Analysis

Automatic Security analysis verifies the ability of the protocol to achieve the designated security goals in the presence of malicious entities. The security analysis tools such as Casper-FDR and Avispa are mathematical frameworks which evaluate the protocol’s behavior in multiple hostile environments with the set of axioms.


### 3.2. Desynchronization Attack Model

This attack model aims to disconnect a valid tag from an identification system by overwriting its dynamic attributes. However, a successful desynchronization attack does not reveal any tag’s information to the adversary. The minimum requirements for the adversary to lunch a desync attack is the ability to eavesdrop and replay public messages. Based on the memory architecture of the RFID system, the execution of the attack can be defined for four different scenarios.Scenario 1 (single copy ofIDS stored on tag and reader’s side).
In this scenario the reader and the tag stores latest copy of identity pseudonym(IDS). The attack executes on such tag/reader pair in two steps.(1)
The adversary keeps track of an authentication session and blocks the challenge messageY from the tag to the reader. As a consequence of this step, the tag’s memory updates whereas the IDS on the reader’s side remains same.(2)
In the next session, the protocol fails at identification stage when theIDS provided by the tag is not found in the reader’s dynamic memory.Table7 shows the status of system’s dynamic memory for each step.Table 7
Status of dynamic memory for Scenario1.
Sessions Reader’s memory Tag’s memory (IDS) (IDS) 1 I D S 1 I D S 1  2 I D S 1 I D S 2Scenario 2 (pair of latestIDS stored at tag’s side).
This scenario is defined for the identification system in which the tag stores a pair of latest identity pseudonyms(IDSNEW,IDSOLD) whereas the reader only stores the most recent copy of (IDSNEW). The model executes in following steps [44]:(1)
Consider a synchronized pair of the tag and the reader. The adversary eavesdrops challenge messageX(X1) and blocks the challenge message Y(Y1). As a result, the tag’s dynamic memory updates (IDS2,IDS1) whereas the reader’s database remains unchanged (IDS1).(2)
The adversary allows the tag/reader pair to undergo an uninterrupted authentication session. The identity verification takes place on the basis ofIDS1. (IDSreader=IDS3;IDStag={IDS3,IDS1}).(3)
In this step the attacker imitates as a valid reader and communicates with the tag based onIDS1. The adversary replays the challenge message X1. As a result, the tag’s dynamic memory updates as IDS2and IDS1 whereas the reader’s memory remains the same, i.e., IDS3.(4)
Since the values ofIDS do not match at the communicating ends, the tag fails in identification stage of preceding authentication sessions.Table8 shows the values of index pseudonyms at the end of each step.Table 8
Status of dynamic memory for Scenario2.
Sessions Reader’s memory Tag’s memory ( I D S N E W ) ( I D S N E W , I D S O L D ) 1 I D S 1 I D S 2 , I D S 1  2 I D S 3 I D S 3 , I D S 1  3 I D S 3 I D S 2 , I D S 1Scenario 3 (pair of latestIDS stored at the reader’s side).
The scenario is defined for such protocols in which the reader stores two copies of dynamic memory(IDSNEW,IDSOLD) and the reader also sends a challenge message M to the tag as the last message of the session. The purpose of this message is to intimate the tag about successful mutual authentication so that its dynamic memory can be updated. The step by step execution of the attack is as follows [45]:(1)
The adversary sniffs the public messagesIDS1,X,Y,M from an ongoing authentication session and then blocks the message M. This prevents the tag to update its dynamic variables, i.e., (IDStag=IDS1;IDSreader={IDS2,IDS1}).(2)
In the next session, the adversary allows the tag-reader pair to communicate on the basis ofIDS1 and blocks message M. This step again updates the reader memory whereas the tag’s memory remains unchanged, i.e., (IDStag=IDS1;IDSreader={IDS3,IDS1}).(3)
In the last session the adversary impersonates as a reader and replays messageXandM recorded from step one. This replay attacks breaks the synchronization among the dynamic variables of the tag and the reader. The final values of dynamic variables at the tag and the reader’s side are (IDStag=IDS2;IDSreader={IDS3,IDS1}).The step by step values of index pseudonyms are given in Table9.Table 9
Status of dynamic memory for Scenario3.
Sessions Reader’s memory Tag’s memory ( I D S N E W , I D S O L D ) ( I D S N E W ) 1 I D S 2 , I D S 1 I D S 1  2 I D S 3 , I D S 1 I D S 1  3 I D S 3 , I D S 1 I D S 2Scenario 4 (pair of latestIDS stored on both sides of the system).
The last scenario is for the protocols that store the pair of latest dynamic variables on both communicating ends. The adversary requires five consecutive authentication sessions to completely disconnect a valid tag from the RFID system. The description of attack is as follows [34]:(1)
In step one, the adversary eavesdrops all the public messages(IDS1,X1,Y1) from an authentication session between a completely synchronized tag/reader pair.(2)
In the next step, the adversary recordsIDS2 and X2 and block X2 at the same time. The dynamic memory of both sides remains unchanged.(3)
In step three, the adversary forces the tag/reader pair authentication on the basis ofIDS1 by blocking the first response of the tag to the reader’s hello message.(4)
In this step, the adversary imitates as the reader and communicates with the tag based on the messages eavesdropped in session one. This step makes the tag partially desynchronized.(5)
The last step comprises of the adversary’s communication with the tag on the basis ofIDS2 and X2. This step completely changes the values of identity pseudonyms stored in the tag’s and the reader’s memory.The working example of the attack is presented in Table10.Table 10
Status of dynamic memory for Scenario4.
Sessions Reader’s memory Tag’s memory ( I D S N E W , I D S O L D ) ( I D S N E W , I D S O L D ) 1 I D S 1 , I D S 0 I D S 1 , I D S 0  2 I D S 1 , I D S 0 I D S 1 , I D S 0  3 I D S 3 , I D S 1 I D S 3 , I D S 1  4 I D S 3 , I D S 1 I D S 2 , I D S 1  5 I D S 3 , I D S 1 I D S ′ , I D S 2The scenarios covered in Tables7, 8, 9, and 10 cover almost all the previous protocols. This proves that nearly every UMAP have been subjected to desynchronization attack which ultimately leads to Denial of Service (DoS). The basic theme of all the DoS attacks is to rewrite the tag’s memory with such previous values of IDS that have been removed from the reader’s memory. The generalized desynchronization attack proved that if the pair of latest dynamic variables are stored at the reader’s side, the tag can be desynchronized in maximum five consecutive sessions, irrespective of its dynamic memory architecture [34].An extended memory buffer for the tag’s dynamic variables at the reader’s database increases the number of sessions required by the adversary to overwrite the tag’s memory. The increase in number of adversary administered session requirements for the execution of desynchronization attack strengthens the protocol’s ability to withstand DoS attacks [46, 47].


### 3.3. Traceability Attack Model

One of the most prominent threats associated with the RFID system is traceability. In this model, the adversary gathers information related to the tag so that it can violate its location privacy at any point of time in future. The UMAPs can resist the traceability attacks by anonymizing the tag’s response to the reader’s queries.According to the formal definition, the tag (T0) is assumed traceable, if the adversary can correctly estimate the value of b when presented with IDSiTb from the set {IDSiT0,IDSiT1} [48, 49]. Two basic models are available in literature to evaluate the strength of the protocol for preserving the anonymity of the tag.


#### 3.3.1. Guess and Determine Model

In guess and determine model, the attacker has following capabilities:(i)
Execute(R,T,i). The attacker can snoop the communication between the tag (T) and the reader (R) during the ith authentication session.(ii)
Send(X,Y,M,i). The adversary can block or alter the message M being communicated between X and Y entities during the identification session i.The traceability attack executes as follows [50, 51]:(i)
Phase 1 (Learning). The attacker gathers information related to the tag under attack by implementing Execute and Send command.(ii)
Phase 2 (Challenge). The attacker is challenged to identify the tag being traced from the set of RFID identifiers.(iii)
Phase 3 (Guess). The attacker continues to gather knowledge through learning phase until it can successfully trace the tag under consideration.


#### 3.3.2. Metaheuristic Model

This model transforms the cryptanalysis of UMAP into a search problem solved with the help of metaheuristic algorithms. The main motivation behind using heuristic search algorithms is their ability to locate global maxima or minima efficiently. The step by step procedure for launching the metaheuristic traceability attack is presented as follows [52]:(1)
The adversary eavesdrops an authentication session between the tag (Tag0) and the reader to obtain public messages X,Y.(2)
The attacker initializes the secret values associated with tag(K,n,ID) by using Mersenne Twister pseudorandom number generator. These initialized values act as a seed for simulated annealing algorithm. The adversary then calculates public messages (X′,Y′) based on assumed secret values.(3)
Simulated Annealing (SA) algorithm is used derive an estimate of(K,n,ID). The values obtained by implementing search algorithm produces public messages that are at minimum deviation from authentic X,Y.(4)
IDSi+1 is calculated by using output of simulated annealing algorithm.(5)
Repeat step (2)-(4) to obtain multiple approximations ofIDSi+1. Final estimate of dynamic pseudonym is obtained by taking majority vector of all approximations.(6)
For the traceability attack final execution, the attacker is presented withIDStagbi+1ϵ{IDStag0i+1,IDStag1i+1}. The successful cryptanalysis depends on correct guess of b by the attacker. In order to estimate the value of b, the attacker calculates a correlation function given in (95).(95)corrIDStagbi+1,IDSi+1=cos⁡IDStagbi+1,IDSi+1=IDStagbi+1·IDSi+1IDStagbi+1·IDSi+1If the correlation between two values is greater than 75%, the tag presented to the adversary istag0 otherwise it is tag1.


### 3.4. Full Disclosure Attack Model

One of the primary features of a UMAP is provision of confidentiality services to the communicating parties. In this cryptanalysis model, the adversary intercepts the public messages to extract sensitive information related to the tag. The full disclosure attack models can be divided into two subcategories:


#### 3.4.1. Ad Hoc Attacks

The ad hoc cryptanalysis also termed as unstructured attacks explore the protocol’s equations to find the mathematical weaknesses. The unstructured attacks exploit the linear behavior of the protocol’s operators to estimate the tag’sID. Table 11 presents a list of UMAPs primitives which exhibit linear behavior. These operators are not preferred for the UMAP design due to their inability to hide the tag’s attributes in public messages.Table 11
Linearized approximations for UMAP's primitives.
Equation Triangular Approximation Comments a  ⋀  b 0   ( P = 0.75 ) [53, 54] a  ∨  b 1   ( P = 0.75 ) [53, 54] a ⊕ 1 a - [46] a ⊕ 0 a [46] ( 1 ∨ b ) ⊕ a a - - ( 0 ∧ b ) ⊕ a a - a + b a i ⊕ b i ⊕ c a r i - 1 c a r i = M a j a i , b i , c a r i - 1 [ 0 < i < L - 1 ] g i v e n   t h a t   c a r 0 = 0 [54] a + b a i ⊕ b i ⊕ c a r a , b , i - 1 c a r a , b , i = a i ∧ b i ∨ [ ( a i ⊕ b i ) ∧ c a r ( a , b , i - 1 ) ] [ 0 < i < L - 1 ] g i v e n   t h a t   c a r a , b , 0 = 0 [55] a - b a i ⊕ b i ⊕ b o r a , b , i - 1 b o r a , b , i = a - i ∧ b i ∨ [ ( a - i ⊕ b i ) ∧ b o r ( a , b , i - 1 ) ] [ 0 < i < L - 1 ] g i v e n   t h a t   b o r a , b , 0 = 0 [55] R o t ( a , 0 ) a [55] R o t ( a , L ) a [55] b = R o t ( a , c ) [ b ] 0 = [ a ] r ( c ) r c = h a m m i n g   w e i g h t   o f   c   o r   m o d   o f   c [55] R o t ( a ⊕ b , a ) a ⊕ b f o r   m o d u l a r   r o t a t i o n   o n l y [54] R o t ( a , c ) ⊕ R o t ( b , c ) R o t ( a ⊕ b , c ) [54]


#### 3.4.2. Structured Attacks

In the structured cryptanalysis models, the adversary follows a predefined set of instructions to breach the confidentiality of an authentication session. The use of probabilistically imbalanced functions as protocol’s primitives reveals the tag’s information in public messages. Some of the common structured attack models are defined as follows:(i)
Tango Attack. The passive tango cryptanalysis is a probabilistic attack which is extremely efficient for recovering the tag’s ID and other secret information related to a tag. The attack comprises two steps: (1) selection of good approximation (GA) equations and (2) manipulation of derived good approximation equations for disclosing the tag’s ID under attack. The details of the attack are elaborated as follows [53, 56]:
(I)
For selection of GA equation, the attacker locally initializes the tag’sID and dynamic variables, who then simulates x UMAP sessions based on the assumed data. The main aim of this step is to obtain a set of GA equations in terms of public parameters {IDS,X,Y} for the tag’s ID estimation. The combinations which exhibits poor diffusion of tag’s ID are selected as GA equations.Once a set of GA is derived, the tag ID of any identifier implementing the UMAP under consideration can be efficiently calculated using (II).(II)
The idea behind this step is to combine the results of GA equations ofα eavesdropped sessions to obtain a single global estimation of ID which is highly correlated with tag’s original ID. The detail procedure of step (II) is elaborated as follows:
(i)
Define a matrixZ of size rxm, where(96)r=L#ofbitsintag’sIDm=#ofGAequations∗#ofevasdroppedsessions=x∗α(ii)
For each eavesdropped session, calculate the values of GA equations and storeLbit results as a row of matrix Z. Repeat this process for α authentication sessions.(iii)
The estimation of tag’sID is obtained by adding each of columns of matrix Z and returning a zero, if the sum of the said column is below a threshold δ. If the sum is greater than or equal to δ; then one is returned. Formula for calculating δ is as follows:(97)δ=0.5∗x∗αThe success probability of tango attack is directly proportional to the number of simulated session and the number of eavesdropped sessions.(ii)
Recursive Linear Cryptanalysis. The Recursive Linear Cryptanalysis (RLC) [54] is applicable to protocols in which the number of secret values associated with the tag under attack is less than or equal to the number of communicating messages per authentication session. This property of protocol makes RLC passive in nature. The attack executes by linearizing the public message encryption equations from a single authentication session in terms of attributes associated with the tag. The linear approximation defines the equation in terms of XOR function only. The rules of linear approximation can be derived from Table 11. If the coefficient matrix of linear system of equations is nonsingular and the system is over defined, full disclosure attack can be successfully executed in bit by bit fashion.(iii)
Recursive Differential Cryptanalysis. The Recursive Differential Cryptanalysis (RDC) [54] is similar to RLC and it is applied when the number of public messages from a single authentication session is less than the number of variables associated with the tag. The RDC is active in nature. The adversary forces the tag-reader set to communicate on the same set of dynamic variables for every session by blocking the IDS and the message Y along with eavesdropping these compromised sessions.This expands the number of equations from which linearized system of equation can be formed. If the coefficient of resulting system of equations is nonsingular, the secrets related to the tag are successfully revealed. The success probability of RDC depends on the number of sessions that needs to be interfered by the adversary for successful execution.The above stated attacks are the primary building blocks for the evaluation of CIAA services offered by the UMAPs. Table12 provides a compact security analysis of existing UMAPs and highlights the vulnerability of authentication protocols to multiple cryptanalysis models.Table 12
Comparative security analysis of UMAPs.
Protocol Desynchronization Attack Traceability Attack Full Disclosure Attack LMAP [57] [58, 59] [57]  M2AP [57] [60] [57]  EMAP [61] [60] [61]  SASI [62] [63] [55, 64, 65]  Gossamer’s Protocol [66] [60] [67]  Yeh et al.’s Protocol [34] [60] [64, 65, 68]  RAPP [42, 69] [45, 70] [24, 67]  RAPLT [34] - - [71]  RCIA [34] [72] - -  SLAP [34] [73] - -The results of comparative analysis presented in Table12 emphasize the need to develop a protocol that is computationally efficient and are robust against structured and nonstructured attacks. The design principles for the development of secure authentication protocol are continuously evolving by virtue of weaknesses highlighted by the cryptanalysis reports of existing UMAPs. Following are the design principles that have been deduced through the cryptanalysis of UMAPs discussed in Section 2.(i)
The reader should storen latest values of dynamic variables associated with the tag. The value of n will be directly proportional to strength against desynchronization attack.(ii)
Introduction of an ultralightweight primitive with strong confusion and diffusion capabilities will improve the confidentiality offered by the UMAP.By incorporating the above-mentioned principles, we can design a UMAP with strong confidentiality, integrity, and availability features. Section4 presents a novel UMAP termed as Extremely Good Privacy protocol along with the detailed security analysis to prove its ability to provide security and privacy to low-cost IoT nodes.


## 3.1. Formal Analysis

The formal analysis is performed to evaluate the protocol’s ability to authenticate the communicating entities under multiple channel conditions. The sequence of challenge/response message exchange between the tag and the reader is examined by virtue of following methods.


### 3.1.1. Logic of Belief Analysis

This method analyzes the public message composition and sequence of interaction between the communicating parties to systematically evaluate the protocol’s functionality on an abstract level. The objectives of logic of belief analysis are as follows:(i)
State what is accomplished by the protocol(ii)
Draw attention to unnecessary actions that can be removed from a protocol(iii)
Highlight any encrypted messages that could be sent in clear textThe prominent mathematical models used for the logic of belief analysis are Burrows–Abadi–Needham (BAN) logic model and Gong–Needham–Yahalom (GNY) logic model.


### 3.1.2. Automated Security Analysis

Automatic Security analysis verifies the ability of the protocol to achieve the designated security goals in the presence of malicious entities. The security analysis tools such as Casper-FDR and Avispa are mathematical frameworks which evaluate the protocol’s behavior in multiple hostile environments with the set of axioms.


## 3.1.1. Logic of Belief Analysis

This method analyzes the public message composition and sequence of interaction between the communicating parties to systematically evaluate the protocol’s functionality on an abstract level. The objectives of logic of belief analysis are as follows:(i)
State what is accomplished by the protocol(ii)
Draw attention to unnecessary actions that can be removed from a protocol(iii)
Highlight any encrypted messages that could be sent in clear textThe prominent mathematical models used for the logic of belief analysis are Burrows–Abadi–Needham (BAN) logic model and Gong–Needham–Yahalom (GNY) logic model.


## 3.1.2. Automated Security Analysis

Automatic Security analysis verifies the ability of the protocol to achieve the designated security goals in the presence of malicious entities. The security analysis tools such as Casper-FDR and Avispa are mathematical frameworks which evaluate the protocol’s behavior in multiple hostile environments with the set of axioms.


## 3.2. Desynchronization Attack Model

This attack model aims to disconnect a valid tag from an identification system by overwriting its dynamic attributes. However, a successful desynchronization attack does not reveal any tag’s information to the adversary. The minimum requirements for the adversary to lunch a desync attack is the ability to eavesdrop and replay public messages. Based on the memory architecture of the RFID system, the execution of the attack can be defined for four different scenarios.Scenario 1 (single copy ofIDS stored on tag and reader’s side).
In this scenario the reader and the tag stores latest copy of identity pseudonym(IDS). The attack executes on such tag/reader pair in two steps.(1)
The adversary keeps track of an authentication session and blocks the challenge messageY from the tag to the reader. As a consequence of this step, the tag’s memory updates whereas the IDS on the reader’s side remains same.(2)
In the next session, the protocol fails at identification stage when theIDS provided by the tag is not found in the reader’s dynamic memory.Table7 shows the status of system’s dynamic memory for each step.Table 7
Status of dynamic memory for Scenario1.
Sessions Reader’s memory Tag’s memory (IDS) (IDS) 1 I D S 1 I D S 1  2 I D S 1 I D S 2Scenario 2 (pair of latestIDS stored at tag’s side).
This scenario is defined for the identification system in which the tag stores a pair of latest identity pseudonyms(IDSNEW,IDSOLD) whereas the reader only stores the most recent copy of (IDSNEW). The model executes in following steps [44]:(1)
Consider a synchronized pair of the tag and the reader. The adversary eavesdrops challenge messageX(X1) and blocks the challenge message Y(Y1). As a result, the tag’s dynamic memory updates (IDS2,IDS1) whereas the reader’s database remains unchanged (IDS1).(2)
The adversary allows the tag/reader pair to undergo an uninterrupted authentication session. The identity verification takes place on the basis ofIDS1. (IDSreader=IDS3;IDStag={IDS3,IDS1}).(3)
In this step the attacker imitates as a valid reader and communicates with the tag based onIDS1. The adversary replays the challenge message X1. As a result, the tag’s dynamic memory updates as IDS2and IDS1 whereas the reader’s memory remains the same, i.e., IDS3.(4)
Since the values ofIDS do not match at the communicating ends, the tag fails in identification stage of preceding authentication sessions.Table8 shows the values of index pseudonyms at the end of each step.Table 8
Status of dynamic memory for Scenario2.
Sessions Reader’s memory Tag’s memory ( I D S N E W ) ( I D S N E W , I D S O L D ) 1 I D S 1 I D S 2 , I D S 1  2 I D S 3 I D S 3 , I D S 1  3 I D S 3 I D S 2 , I D S 1Scenario 3 (pair of latestIDS stored at the reader’s side).
The scenario is defined for such protocols in which the reader stores two copies of dynamic memory(IDSNEW,IDSOLD) and the reader also sends a challenge message M to the tag as the last message of the session. The purpose of this message is to intimate the tag about successful mutual authentication so that its dynamic memory can be updated. The step by step execution of the attack is as follows [45]:(1)
The adversary sniffs the public messagesIDS1,X,Y,M from an ongoing authentication session and then blocks the message M. This prevents the tag to update its dynamic variables, i.e., (IDStag=IDS1;IDSreader={IDS2,IDS1}).(2)
In the next session, the adversary allows the tag-reader pair to communicate on the basis ofIDS1 and blocks message M. This step again updates the reader memory whereas the tag’s memory remains unchanged, i.e., (IDStag=IDS1;IDSreader={IDS3,IDS1}).(3)
In the last session the adversary impersonates as a reader and replays messageXandM recorded from step one. This replay attacks breaks the synchronization among the dynamic variables of the tag and the reader. The final values of dynamic variables at the tag and the reader’s side are (IDStag=IDS2;IDSreader={IDS3,IDS1}).The step by step values of index pseudonyms are given in Table9.Table 9
Status of dynamic memory for Scenario3.
Sessions Reader’s memory Tag’s memory ( I D S N E W , I D S O L D ) ( I D S N E W ) 1 I D S 2 , I D S 1 I D S 1  2 I D S 3 , I D S 1 I D S 1  3 I D S 3 , I D S 1 I D S 2Scenario 4 (pair of latestIDS stored on both sides of the system).
The last scenario is for the protocols that store the pair of latest dynamic variables on both communicating ends. The adversary requires five consecutive authentication sessions to completely disconnect a valid tag from the RFID system. The description of attack is as follows [34]:(1)
In step one, the adversary eavesdrops all the public messages(IDS1,X1,Y1) from an authentication session between a completely synchronized tag/reader pair.(2)
In the next step, the adversary recordsIDS2 and X2 and block X2 at the same time. The dynamic memory of both sides remains unchanged.(3)
In step three, the adversary forces the tag/reader pair authentication on the basis ofIDS1 by blocking the first response of the tag to the reader’s hello message.(4)
In this step, the adversary imitates as the reader and communicates with the tag based on the messages eavesdropped in session one. This step makes the tag partially desynchronized.(5)
The last step comprises of the adversary’s communication with the tag on the basis ofIDS2 and X2. This step completely changes the values of identity pseudonyms stored in the tag’s and the reader’s memory.The working example of the attack is presented in Table10.Table 10
Status of dynamic memory for Scenario4.
Sessions Reader’s memory Tag’s memory ( I D S N E W , I D S O L D ) ( I D S N E W , I D S O L D ) 1 I D S 1 , I D S 0 I D S 1 , I D S 0  2 I D S 1 , I D S 0 I D S 1 , I D S 0  3 I D S 3 , I D S 1 I D S 3 , I D S 1  4 I D S 3 , I D S 1 I D S 2 , I D S 1  5 I D S 3 , I D S 1 I D S ′ , I D S 2The scenarios covered in Tables7, 8, 9, and 10 cover almost all the previous protocols. This proves that nearly every UMAP have been subjected to desynchronization attack which ultimately leads to Denial of Service (DoS). The basic theme of all the DoS attacks is to rewrite the tag’s memory with such previous values of IDS that have been removed from the reader’s memory. The generalized desynchronization attack proved that if the pair of latest dynamic variables are stored at the reader’s side, the tag can be desynchronized in maximum five consecutive sessions, irrespective of its dynamic memory architecture [34].An extended memory buffer for the tag’s dynamic variables at the reader’s database increases the number of sessions required by the adversary to overwrite the tag’s memory. The increase in number of adversary administered session requirements for the execution of desynchronization attack strengthens the protocol’s ability to withstand DoS attacks [46, 47].


## 3.3. Traceability Attack Model

One of the most prominent threats associated with the RFID system is traceability. In this model, the adversary gathers information related to the tag so that it can violate its location privacy at any point of time in future. The UMAPs can resist the traceability attacks by anonymizing the tag’s response to the reader’s queries.According to the formal definition, the tag (T0) is assumed traceable, if the adversary can correctly estimate the value of b when presented with IDSiTb from the set {IDSiT0,IDSiT1} [48, 49]. Two basic models are available in literature to evaluate the strength of the protocol for preserving the anonymity of the tag.


### 3.3.1. Guess and Determine Model

In guess and determine model, the attacker has following capabilities:(i)
Execute(R,T,i). The attacker can snoop the communication between the tag (T) and the reader (R) during the ith authentication session.(ii)
Send(X,Y,M,i). The adversary can block or alter the message M being communicated between X and Y entities during the identification session i.The traceability attack executes as follows [50, 51]:(i)
Phase 1 (Learning). The attacker gathers information related to the tag under attack by implementing Execute and Send command.(ii)
Phase 2 (Challenge). The attacker is challenged to identify the tag being traced from the set of RFID identifiers.(iii)
Phase 3 (Guess). The attacker continues to gather knowledge through learning phase until it can successfully trace the tag under consideration.


### 3.3.2. Metaheuristic Model

This model transforms the cryptanalysis of UMAP into a search problem solved with the help of metaheuristic algorithms. The main motivation behind using heuristic search algorithms is their ability to locate global maxima or minima efficiently. The step by step procedure for launching the metaheuristic traceability attack is presented as follows [52]:(1)
The adversary eavesdrops an authentication session between the tag (Tag0) and the reader to obtain public messages X,Y.(2)
The attacker initializes the secret values associated with tag(K,n,ID) by using Mersenne Twister pseudorandom number generator. These initialized values act as a seed for simulated annealing algorithm. The adversary then calculates public messages (X′,Y′) based on assumed secret values.(3)
Simulated Annealing (SA) algorithm is used derive an estimate of(K,n,ID). The values obtained by implementing search algorithm produces public messages that are at minimum deviation from authentic X,Y.(4)
IDSi+1 is calculated by using output of simulated annealing algorithm.(5)
Repeat step (2)-(4) to obtain multiple approximations ofIDSi+1. Final estimate of dynamic pseudonym is obtained by taking majority vector of all approximations.(6)
For the traceability attack final execution, the attacker is presented withIDStagbi+1ϵ{IDStag0i+1,IDStag1i+1}. The successful cryptanalysis depends on correct guess of b by the attacker. In order to estimate the value of b, the attacker calculates a correlation function given in (95).(95)corrIDStagbi+1,IDSi+1=cos⁡IDStagbi+1,IDSi+1=IDStagbi+1·IDSi+1IDStagbi+1·IDSi+1If the correlation between two values is greater than 75%, the tag presented to the adversary istag0 otherwise it is tag1.


## 3.3.1. Guess and Determine Model

In guess and determine model, the attacker has following capabilities:(i)
Execute(R,T,i). The attacker can snoop the communication between the tag (T) and the reader (R) during the ith authentication session.(ii)
Send(X,Y,M,i). The adversary can block or alter the message M being communicated between X and Y entities during the identification session i.The traceability attack executes as follows [50, 51]:(i)
Phase 1 (Learning). The attacker gathers information related to the tag under attack by implementing Execute and Send command.(ii)
Phase 2 (Challenge). The attacker is challenged to identify the tag being traced from the set of RFID identifiers.(iii)
Phase 3 (Guess). The attacker continues to gather knowledge through learning phase until it can successfully trace the tag under consideration.


## 3.3.2. Metaheuristic Model

This model transforms the cryptanalysis of UMAP into a search problem solved with the help of metaheuristic algorithms. The main motivation behind using heuristic search algorithms is their ability to locate global maxima or minima efficiently. The step by step procedure for launching the metaheuristic traceability attack is presented as follows [52]:(1)
The adversary eavesdrops an authentication session between the tag (Tag0) and the reader to obtain public messages X,Y.(2)
The attacker initializes the secret values associated with tag(K,n,ID) by using Mersenne Twister pseudorandom number generator. These initialized values act as a seed for simulated annealing algorithm. The adversary then calculates public messages (X′,Y′) based on assumed secret values.(3)
Simulated Annealing (SA) algorithm is used derive an estimate of(K,n,ID). The values obtained by implementing search algorithm produces public messages that are at minimum deviation from authentic X,Y.(4)
IDSi+1 is calculated by using output of simulated annealing algorithm.(5)
Repeat step (2)-(4) to obtain multiple approximations ofIDSi+1. Final estimate of dynamic pseudonym is obtained by taking majority vector of all approximations.(6)
For the traceability attack final execution, the attacker is presented withIDStagbi+1ϵ{IDStag0i+1,IDStag1i+1}. The successful cryptanalysis depends on correct guess of b by the attacker. In order to estimate the value of b, the attacker calculates a correlation function given in (95).(95)corrIDStagbi+1,IDSi+1=cos⁡IDStagbi+1,IDSi+1=IDStagbi+1·IDSi+1IDStagbi+1·IDSi+1If the correlation between two values is greater than 75%, the tag presented to the adversary istag0 otherwise it is tag1.


## 3.4. Full Disclosure Attack Model

One of the primary features of a UMAP is provision of confidentiality services to the communicating parties. In this cryptanalysis model, the adversary intercepts the public messages to extract sensitive information related to the tag. The full disclosure attack models can be divided into two subcategories:


### 3.4.1. Ad Hoc Attacks

The ad hoc cryptanalysis also termed as unstructured attacks explore the protocol’s equations to find the mathematical weaknesses. The unstructured attacks exploit the linear behavior of the protocol’s operators to estimate the tag’sID. Table 11 presents a list of UMAPs primitives which exhibit linear behavior. These operators are not preferred for the UMAP design due to their inability to hide the tag’s attributes in public messages.Table 11
Linearized approximations for UMAP's primitives.
Equation Triangular Approximation Comments a  ⋀  b 0   ( P = 0.75 ) [53, 54] a  ∨  b 1   ( P = 0.75 ) [53, 54] a ⊕ 1 a - [46] a ⊕ 0 a [46] ( 1 ∨ b ) ⊕ a a - - ( 0 ∧ b ) ⊕ a a - a + b a i ⊕ b i ⊕ c a r i - 1 c a r i = M a j a i , b i , c a r i - 1 [ 0 < i < L - 1 ] g i v e n   t h a t   c a r 0 = 0 [54] a + b a i ⊕ b i ⊕ c a r a , b , i - 1 c a r a , b , i = a i ∧ b i ∨ [ ( a i ⊕ b i ) ∧ c a r ( a , b , i - 1 ) ] [ 0 < i < L - 1 ] g i v e n   t h a t   c a r a , b , 0 = 0 [55] a - b a i ⊕ b i ⊕ b o r a , b , i - 1 b o r a , b , i = a - i ∧ b i ∨ [ ( a - i ⊕ b i ) ∧ b o r ( a , b , i - 1 ) ] [ 0 < i < L - 1 ] g i v e n   t h a t   b o r a , b , 0 = 0 [55] R o t ( a , 0 ) a [55] R o t ( a , L ) a [55] b = R o t ( a , c ) [ b ] 0 = [ a ] r ( c ) r c = h a m m i n g   w e i g h t   o f   c   o r   m o d   o f   c [55] R o t ( a ⊕ b , a ) a ⊕ b f o r   m o d u l a r   r o t a t i o n   o n l y [54] R o t ( a , c ) ⊕ R o t ( b , c ) R o t ( a ⊕ b , c ) [54]


### 3.4.2. Structured Attacks

In the structured cryptanalysis models, the adversary follows a predefined set of instructions to breach the confidentiality of an authentication session. The use of probabilistically imbalanced functions as protocol’s primitives reveals the tag’s information in public messages. Some of the common structured attack models are defined as follows:(i)
Tango Attack. The passive tango cryptanalysis is a probabilistic attack which is extremely efficient for recovering the tag’s ID and other secret information related to a tag. The attack comprises two steps: (1) selection of good approximation (GA) equations and (2) manipulation of derived good approximation equations for disclosing the tag’s ID under attack. The details of the attack are elaborated as follows [53, 56]:
(I)
For selection of GA equation, the attacker locally initializes the tag’sID and dynamic variables, who then simulates x UMAP sessions based on the assumed data. The main aim of this step is to obtain a set of GA equations in terms of public parameters {IDS,X,Y} for the tag’s ID estimation. The combinations which exhibits poor diffusion of tag’s ID are selected as GA equations.Once a set of GA is derived, the tag ID of any identifier implementing the UMAP under consideration can be efficiently calculated using (II).(II)
The idea behind this step is to combine the results of GA equations ofα eavesdropped sessions to obtain a single global estimation of ID which is highly correlated with tag’s original ID. The detail procedure of step (II) is elaborated as follows:
(i)
Define a matrixZ of size rxm, where(96)r=L#ofbitsintag’sIDm=#ofGAequations∗#ofevasdroppedsessions=x∗α(ii)
For each eavesdropped session, calculate the values of GA equations and storeLbit results as a row of matrix Z. Repeat this process for α authentication sessions.(iii)
The estimation of tag’sID is obtained by adding each of columns of matrix Z and returning a zero, if the sum of the said column is below a threshold δ. If the sum is greater than or equal to δ; then one is returned. Formula for calculating δ is as follows:(97)δ=0.5∗x∗αThe success probability of tango attack is directly proportional to the number of simulated session and the number of eavesdropped sessions.(ii)
Recursive Linear Cryptanalysis. The Recursive Linear Cryptanalysis (RLC) [54] is applicable to protocols in which the number of secret values associated with the tag under attack is less than or equal to the number of communicating messages per authentication session. This property of protocol makes RLC passive in nature. The attack executes by linearizing the public message encryption equations from a single authentication session in terms of attributes associated with the tag. The linear approximation defines the equation in terms of XOR function only. The rules of linear approximation can be derived from Table 11. If the coefficient matrix of linear system of equations is nonsingular and the system is over defined, full disclosure attack can be successfully executed in bit by bit fashion.(iii)
Recursive Differential Cryptanalysis. The Recursive Differential Cryptanalysis (RDC) [54] is similar to RLC and it is applied when the number of public messages from a single authentication session is less than the number of variables associated with the tag. The RDC is active in nature. The adversary forces the tag-reader set to communicate on the same set of dynamic variables for every session by blocking the IDS and the message Y along with eavesdropping these compromised sessions.This expands the number of equations from which linearized system of equation can be formed. If the coefficient of resulting system of equations is nonsingular, the secrets related to the tag are successfully revealed. The success probability of RDC depends on the number of sessions that needs to be interfered by the adversary for successful execution.The above stated attacks are the primary building blocks for the evaluation of CIAA services offered by the UMAPs. Table12 provides a compact security analysis of existing UMAPs and highlights the vulnerability of authentication protocols to multiple cryptanalysis models.Table 12
Comparative security analysis of UMAPs.
Protocol Desynchronization Attack Traceability Attack Full Disclosure Attack LMAP [57] [58, 59] [57]  M2AP [57] [60] [57]  EMAP [61] [60] [61]  SASI [62] [63] [55, 64, 65]  Gossamer’s Protocol [66] [60] [67]  Yeh et al.’s Protocol [34] [60] [64, 65, 68]  RAPP [42, 69] [45, 70] [24, 67]  RAPLT [34] - - [71]  RCIA [34] [72] - -  SLAP [34] [73] - -The results of comparative analysis presented in Table12 emphasize the need to develop a protocol that is computationally efficient and are robust against structured and nonstructured attacks. The design principles for the development of secure authentication protocol are continuously evolving by virtue of weaknesses highlighted by the cryptanalysis reports of existing UMAPs. Following are the design principles that have been deduced through the cryptanalysis of UMAPs discussed in Section 2.(i)
The reader should storen latest values of dynamic variables associated with the tag. The value of n will be directly proportional to strength against desynchronization attack.(ii)
Introduction of an ultralightweight primitive with strong confusion and diffusion capabilities will improve the confidentiality offered by the UMAP.By incorporating the above-mentioned principles, we can design a UMAP with strong confidentiality, integrity, and availability features. Section4 presents a novel UMAP termed as Extremely Good Privacy protocol along with the detailed security analysis to prove its ability to provide security and privacy to low-cost IoT nodes.


## 3.4.1. Ad Hoc Attacks

The ad hoc cryptanalysis also termed as unstructured attacks explore the protocol’s equations to find the mathematical weaknesses. The unstructured attacks exploit the linear behavior of the protocol’s operators to estimate the tag’sID. Table 11 presents a list of UMAPs primitives which exhibit linear behavior. These operators are not preferred for the UMAP design due to their inability to hide the tag’s attributes in public messages.Table 11
Linearized approximations for UMAP's primitives.
Equation Triangular Approximation Comments a  ⋀  b 0   ( P = 0.75 ) [53, 54] a  ∨  b 1   ( P = 0.75 ) [53, 54] a ⊕ 1 a - [46] a ⊕ 0 a [46] ( 1 ∨ b ) ⊕ a a - - ( 0 ∧ b ) ⊕ a a - a + b a i ⊕ b i ⊕ c a r i - 1 c a r i = M a j a i , b i , c a r i - 1 [ 0 < i < L - 1 ] g i v e n   t h a t   c a r 0 = 0 [54] a + b a i ⊕ b i ⊕ c a r a , b , i - 1 c a r a , b , i = a i ∧ b i ∨ [ ( a i ⊕ b i ) ∧ c a r ( a , b , i - 1 ) ] [ 0 < i < L - 1 ] g i v e n   t h a t   c a r a , b , 0 = 0 [55] a - b a i ⊕ b i ⊕ b o r a , b , i - 1 b o r a , b , i = a - i ∧ b i ∨ [ ( a - i ⊕ b i ) ∧ b o r ( a , b , i - 1 ) ] [ 0 < i < L - 1 ] g i v e n   t h a t   b o r a , b , 0 = 0 [55] R o t ( a , 0 ) a [55] R o t ( a , L ) a [55] b = R o t ( a , c ) [ b ] 0 = [ a ] r ( c ) r c = h a m m i n g   w e i g h t   o f   c   o r   m o d   o f   c [55] R o t ( a ⊕ b , a ) a ⊕ b f o r   m o d u l a r   r o t a t i o n   o n l y [54] R o t ( a , c ) ⊕ R o t ( b , c ) R o t ( a ⊕ b , c ) [54]


## 3.4.2. Structured Attacks

In the structured cryptanalysis models, the adversary follows a predefined set of instructions to breach the confidentiality of an authentication session. The use of probabilistically imbalanced functions as protocol’s primitives reveals the tag’s information in public messages. Some of the common structured attack models are defined as follows:(i)
Tango Attack. The passive tango cryptanalysis is a probabilistic attack which is extremely efficient for recovering the tag’s ID and other secret information related to a tag. The attack comprises two steps: (1) selection of good approximation (GA) equations and (2) manipulation of derived good approximation equations for disclosing the tag’s ID under attack. The details of the attack are elaborated as follows [53, 56]:
(I)
For selection of GA equation, the attacker locally initializes the tag’sID and dynamic variables, who then simulates x UMAP sessions based on the assumed data. The main aim of this step is to obtain a set of GA equations in terms of public parameters {IDS,X,Y} for the tag’s ID estimation. The combinations which exhibits poor diffusion of tag’s ID are selected as GA equations.Once a set of GA is derived, the tag ID of any identifier implementing the UMAP under consideration can be efficiently calculated using (II).(II)
The idea behind this step is to combine the results of GA equations ofα eavesdropped sessions to obtain a single global estimation of ID which is highly correlated with tag’s original ID. The detail procedure of step (II) is elaborated as follows:
(i)
Define a matrixZ of size rxm, where(96)r=L#ofbitsintag’sIDm=#ofGAequations∗#ofevasdroppedsessions=x∗α(ii)
For each eavesdropped session, calculate the values of GA equations and storeLbit results as a row of matrix Z. Repeat this process for α authentication sessions.(iii)
The estimation of tag’sID is obtained by adding each of columns of matrix Z and returning a zero, if the sum of the said column is below a threshold δ. If the sum is greater than or equal to δ; then one is returned. Formula for calculating δ is as follows:(97)δ=0.5∗x∗αThe success probability of tango attack is directly proportional to the number of simulated session and the number of eavesdropped sessions.(ii)
Recursive Linear Cryptanalysis. The Recursive Linear Cryptanalysis (RLC) [54] is applicable to protocols in which the number of secret values associated with the tag under attack is less than or equal to the number of communicating messages per authentication session. This property of protocol makes RLC passive in nature. The attack executes by linearizing the public message encryption equations from a single authentication session in terms of attributes associated with the tag. The linear approximation defines the equation in terms of XOR function only. The rules of linear approximation can be derived from Table 11. If the coefficient matrix of linear system of equations is nonsingular and the system is over defined, full disclosure attack can be successfully executed in bit by bit fashion.(iii)
Recursive Differential Cryptanalysis. The Recursive Differential Cryptanalysis (RDC) [54] is similar to RLC and it is applied when the number of public messages from a single authentication session is less than the number of variables associated with the tag. The RDC is active in nature. The adversary forces the tag-reader set to communicate on the same set of dynamic variables for every session by blocking the IDS and the message Y along with eavesdropping these compromised sessions.This expands the number of equations from which linearized system of equation can be formed. If the coefficient of resulting system of equations is nonsingular, the secrets related to the tag are successfully revealed. The success probability of RDC depends on the number of sessions that needs to be interfered by the adversary for successful execution.The above stated attacks are the primary building blocks for the evaluation of CIAA services offered by the UMAPs. Table12 provides a compact security analysis of existing UMAPs and highlights the vulnerability of authentication protocols to multiple cryptanalysis models.Table 12
Comparative security analysis of UMAPs.
Protocol Desynchronization Attack Traceability Attack Full Disclosure Attack LMAP [57] [58, 59] [57]  M2AP [57] [60] [57]  EMAP [61] [60] [61]  SASI [62] [63] [55, 64, 65]  Gossamer’s Protocol [66] [60] [67]  Yeh et al.’s Protocol [34] [60] [64, 65, 68]  RAPP [42, 69] [45, 70] [24, 67]  RAPLT [34] - - [71]  RCIA [34] [72] - -  SLAP [34] [73] - -The results of comparative analysis presented in Table12 emphasize the need to develop a protocol that is computationally efficient and are robust against structured and nonstructured attacks. The design principles for the development of secure authentication protocol are continuously evolving by virtue of weaknesses highlighted by the cryptanalysis reports of existing UMAPs. Following are the design principles that have been deduced through the cryptanalysis of UMAPs discussed in Section 2.(i)
The reader should storen latest values of dynamic variables associated with the tag. The value of n will be directly proportional to strength against desynchronization attack.(ii)
Introduction of an ultralightweight primitive with strong confusion and diffusion capabilities will improve the confidentiality offered by the UMAP.By incorporating the above-mentioned principles, we can design a UMAP with strong confidentiality, integrity, and availability features. Section4 presents a novel UMAP termed as Extremely Good Privacy protocol along with the detailed security analysis to prove its ability to provide security and privacy to low-cost IoT nodes.


## 4. Extremely Good Privacy Protocol

In this section, we propose a new UMAP which requires few on-chip resources and provides Extremely Good Privacy (EGP). The proposed protocol avoids all unbalanced logical operations (such asAND; OR) and involves only two extremely lightweight operations: XOR&Per-XOR. The new ultralightweight primitive “Per-XOR” inspired from permutation function (Per) introduced in [4], since the later primitive discloses the information of operands, therefore found unsuitable for UMAPs. Moreover, we have also introduced the concept of “inverse permutation” at the tag side which utilizes the permutation function efficiently and with the incorporation of inverse function now it does not require any other primitive to protect its contents. For better understanding of Px primitive and Px-1, consider the following.(A) Computation of Per-XOR ( P x ). Suppose m&n are two l-bit strings, where(98)m=m1m2…ml,mi∈0,1,i=1,2,…,ln=n1n2…nl,ni∈0,1,i=1,2,…,lThe computation ofPx(m,n) involves two following steps:(1)
Permute (transposition) the string ′m′ according to the string ′n′, by checking each ith bit of the string ′n′ (starting from LSB). If ni=0 then the bit stored at mi will be placed at ml location (LSB); otherwise it will be placed at the same position. In the next clock cycle, if ni+1=0 then the bit stored at mi+1 will be placed at ml-1 location; otherwise it will shifted-left (LSB side). This process will continue till we reach to MSB of string ′n′(nl). After completion, we will have a new string ′m∗′ which is the permuted version of string ′m′.(2)
TakeXOR between the new string ′m∗′ and the string ′n′.Figure14 shows the example of Per-XOR computation with reduced bit length.Figure 14
Computation (example) of Per-XOR (Px).(B) Computation of Inverse Per-XOR ( P x - 1 ). The tag uses Px-1 primitive extensively in order to retrieve the concealed secrets. The computation of Px-1 also involves two steps:(1)
Take XOR between the receivedPx(m,n) and preshared secret n.(2)
Perform inverse permutation in a sequential manner to get the concealed string ′m′. For inverse permutation, we use one pointer/indexer (X) for traversing over the result computed in step-1. If ni=0 then the pointer X moves to ml position and bit stored on lth location on string m will be placed at m1 location; otherwise the pointer X moves to mi position and bit stored on ith location will be placed m1 location. This process will continue till the last bit of the string ‘′n′nl.For better understanding, Figure15 shows the example of Inverse Per-XOR (Px-1) with reduced bit length.Figure 15
Computation (example) of inverse Per-XOR (Px-1).


### 4.1. Working of the EGP Protocol

Figure16 shows the detailed working of the protocol. The EGP protocol involves three main components: Tag (T), Reader (R), and the backend database D. Each ′T′ contains the one static secret ID; two sets of IDS and keys (Old and new). To avoid the possible desynchronization attacks, the ′R′ uses the buffer-based security framework proposed in [46]. In the buffer-based security framework, the reader maintains a dynamic memory architecture and stores all previous pseudonyms and keys (depending upon buffer size). To avoid buffer overflow, a RTC (Real Time Clock) has also been integrated at the reader side that manages the storage of variable. The basic symbols and notations used in this protocol are presented in Table 13.Table 13
Notations used in EGP.
Symbol Meaning P x ( a , b ) Per-XORb with a  P x - 1 ( a , b ) Inverse Per-XORb with a  ⨁ XOR  ∥ Concatenation  K Key  ′R′ Reader  ′T′ TagFigure 16
Block diagram of EGP protocol.The specifications of the protocol are as follows:(1)
The ′R′ initiates the protocol session by sending “hello” message towards the ′T′.(2)
Upon receiving of this query, the ′T′ responds with its current IDS.(3)
The ′R′ looks for the received IDS in its database and if a match occurs then it computes A,B, and C messages and sends to the reader. Otherwise, it will send another “hello” towards ′T′ and repeat the same process of finding matched entry. If the ′R′ does not find the matched entry in this second round, it will terminate the protocol session.(4)
On receiving ofA,B, and C messages, the ′T′ performs following three tasks:
(a)
Extract random nonce(n1,n2) from messages A&B:(99)n1=Px-1A,K(100)n2=Px-1B,K⊕n1(5)
Compute the local value ofC and compare it with the received C. If both of the values coincide, only then the ′T′ authenticates ′R′; otherwise it will terminate the protocol session with the particular ′R′. After successful authentication, the ′T′ computes the message D and transmits towards ′R′.(6)
UpdateIDS and key (Knext).(7)
Upon receiving of messageD, the ′R′ computes a local value ofD and compares it with the received one. If both values coincide then the ′R′ authenticates ′T′ and updates IDS andkey for the particular ′T′ in its database for future correspondence.Figure16 presents the block diagram of the EGP protocol.


### 4.2. Security Analysis of EGP Protocol

We analyze the security of the proposed protocol in two aspects: formal verification and resistance of the protocol against rudimentary attacks. The detailed description of the security analysis is presented as follows.


#### 4.2.1. Formal Security Analysis

For formal security verification, we use GNY logic. The formal analysis tool uses abstract language and verifies the assumptions and objectives of the security algorithms. The detailed description of the analysis is as follows.(1) GNY Logic Analysis.GNY (Gong–Needham–Yahalom) logic is a mathematical formal verification tool that verifies the security assumptions and goals of security algorithms. The GNY logic is a multistep process which first translates the assumptions and public messages in abstract language and then starts validating goals. For validation of the goals, the GNY logic uses three rules: Being Informed, Possession, and Freshness Rules.(a)
Being Informed Rules. Any formula that M receives is considered as “being informed”.I1: if M is informed the formula N, which he did not convey in this run, then M is informed N(101)I1:M⊲*NM⊲NI2: if M is informed an encrypted formula with symmetric key (K) then M is informed the formula.(102)I2:M⊲NK,M∋NM⊲N(b)
Possession Rules. If M possesses a formula then it can possess other associated formulae as well.P1: M can possess any variable which is being informed(103)P1:M⊲NM∋NP2: if M possess two different formulae then it can possess their concatenation and functions as well.(104)P2:M∋N,M∋OM∋N,O,M∋FN,OTable 14 enlists the notations used in GNY logic analysis.(c)
Freshness Rules. On the basis of belief, M determines the freshness of messages.F1: if M believes that a formula is fresh then he also believes that any concatenation and function will be fresh.(105)F1:M≡#NM≡#N,O,M≡#FN,OTable 14
Notations used in GNY logic analysis.
S.No. Statement/Notations Interpretation 1 M Manager/Administrator  2 N Message/variable  3 R Reader  4 T Tag  5 I S Intermediate Step  6 M ⊲ ∗ N M is informed N, M didn’t convey in current session  7 M⊲N M is informed N  8 ( N ∥ O ) Concatenation ofN&O  9 M | ≡ # ( N ) M believes that Nis fresh  10 M | ≡ φ ( N ) M believes that Nis computable/recognizable  11 M | ≡ N M believes that N holds  12 M | ≡ M ↔ K Z M believes that Kis an appropriate secret for Z  13 M ∋ N M can possess N  14 M | ~ N M once conveyed N  15 N K Nis encrypted using symmetric key K(2) Formal Proof of EGP Using GNY Logic.The first step in GNY analysis is to describe the assumptions of the protocols which are followed by the formalization of the exchanged messages. Finally, the goals of the protocols are verified using formal analysis postulates.The authentication process mainly depends upon the pseudorandom numbers; therefore we apply analysis on first two messages only.The messages can be formulated as follows:(106)T⊲∗n1K~>R≡T↔KRT⊲∗n2n1,K~>R≡T↔n1,KRThe goal of sending such messages is(107)G1:T≡R∋n1,n2By applying the verification postulates, we can validate EGP’s goal as follows:(108)T⊲∗n1K~>R≡T↔KRIS1:T⊲*n1KSinceR≡T↔KRisalreadyassumedtobesatisfiedBy consideringI1,S4, and I2 we can have(109)IS2:T⊲n1KIS2:T⊲n1According to ruleP1, we get(110)IS3:T∋n1Now for second message as we know,(111)T⊲∗n2n1,K~>R≡T↔n1,KRIS4:T⊲*n2n1,KSinceIS3andR≡T↔KRisalreadyassumedtobesatisfiedIf we considerI1,S4, and I2 then IS4 can be represented as(112)IS5:T⊲n2n1,KIS6:T⊲n2FurtherIS6 can be interpreted as(113)IS7:T∋n2Hence fromIS3 and IS7, it can be observed that EGP optimally achieves its goal:(114)T≡R∋n1,n2If adversary tries to modifyn1, then effect of this alteration directly transfers to n2 as well. The tag will not verify message C, hence abort such protocol sessions, and will remain synchronized.


### 4.3. Desynchronization Attack

The desynchronization attacks presented in [34] force the legitimate readers and the tags to update different pair of pseudonyms and keys and therefore make the resources unavailable for the legitimate parties. To avoid such availability and desynchronization attacks, the EGP protocol uses dynamic memory architecture at the reader’s side. This memory architecture involves RTC (Real Time Clock) and Shift Registers to store the current and previous values of pseudonyms and keys of each associated tag. The memory architecture is located at the reader’s side and therefore does not increase the cost of the tag. If the adversary tries to block some genuine authentication sessions and uses replay attack models to desynchronize the EGP’ tag and the reader then this will be impossible for the adversary, since the reader keeps the records of n authentication sessions. The size of dynamic variable buffer at the reader’s side primarily depends on the architecture of the database associated with the network. The increase in buffer size enhances the synchronization of the tag/reader pair at the cost of increased memory requirement at the reader’s side.


### 4.4. Traceability Attack

In EGP if an adversary tries to find the conjunctureID through publically disclosed messages then because of optimal messages structure, she will get only ambiguous equation:(115)ID=Px-1D,Px-1C,K⊕px-1B,K⊕Px-1A,KBy keeping in view of computational complexity of (115), it will be almost impossible for an adversary to track the individual tag by resolving this equation. Moreover, most of the variables involved in EGP will get update after each authentication session; therefore EGP proves to be secure against all existing traceability attack models.


### 4.5. Full Disclosure Attack

The full disclosure attacks exploit the inherent weaknesses of theT-functions. The attackers usually perform different computational operations on public messages and try to obtain conjecture secret values. However, the inclusion of nontriangular primitive Per-XOR and inversePer-XOR makes EGP protocol almost impossible to retrieve the concealed secret from public messages. The protocol’s performance to unstructured and structured full disclosure attack is described as follows:(A)
Ad Hoc Attack. The ad hoc attacks target the lack of randomness in public messages and the linear behavior of the protocol’s primitives. In EGP protocol, the structure of the public messages is designed to avoid the previously presented unstructured full disclosure attacks. Every public message increments the degree of randomness by one; i.e., message A consists of random number n1, message B consists of n2 and n1, and message C consists of K∗,n2, and n1. Even if the adversary keeps the dynamic variables constant for multiple sessions by blocking the message D, the values of n1,n2, and K∗ change for every session and hence the values of public messages vary making it theoretically impossible to derive the tag’s ID by just eavesdropping the authentication sessions.In addition to this, thePer-XOR operator provides improved confusion and diffusion services to the public messages due to the following features:
(1)
TheXor operation masks the result of permutation making it impossible to reveal the LSB or MSB of the first operand of Per-Xor function without complete information of the second operand.(2)
The operands of thePer-Xor function in the EGP protocol are the irreversible combination of dynamic variables. The analysis of message D(Px(K∗⊕ID⊕n1,n2)) shows that even if the adversary obtains K∗⊕ID⊕n1 by exploiting the reversable nature of Per-Xor, the ID cannot be retrieved without the knowledge of K∗ and n1. This enables the presented primitive to effectively conceal the secret values associated with the session in public messages.In [45], an ad hoc full disclosure attack on the RAPP protocol is presented. In the proposed attack, the dynamic variables are kept constant by blocking the last message from the R to the T and then the weakness of permutation primitive is exploited to obtain the random number n1that eventually leads to disclosure of the tag’s ID. For the estimation of single random number, the adversary generates a database of two public messages consisting of constants IDS, K1,K2, and K3.In EGP protocol, the dynamic variables on the tag’s side can be kept constant by blocking messageD from the T to the R. This leaves the adversary with only three public messages (A,B,C) based on constant IDS and K. Since the EGP protocol uses two random numbers (n1,n2), the number of public messages is not sufficient to estimate the private keys generated by the R.Therefore, due to nonlinear behavior ofPer-Xor function and small number of public messages, the ad hoc attacks proposed for RAPP protocol are not applicable to the EGP protocol.(B)
Tango Attack. The tango attack proves to be unsuccessful against nontriangular based UMAPs. The inventors of the tango attack also highlighted this inherent weakness of the attack model. In EGP, we have extensively used nontriangular primitives (Per-XOR and InversePer-XOR) in its design, which requires extensive computational complexity O(8×2K×log2K!×log2n1!×log⁡(n2!) to retrieve ID. Therefore, it is almost impossible for an adversary to find the optimal GA equations and apply tango attack model on EGP.(C)
Recursive Linear and Differential Cryptanalysis. The RLC model exploits the weak diffusion properties of the protocols and uses the public messages to construct the set of linear equations for each individual bit of the concealed secrets. After constructing the sufficient equations, the adversary solves the equations recursively and tries to get the concealed secrets bit by bit. However, the incorporation of (optimal) nontriangular primitives such as recursive hash [41], Psuedo-Kasami codes [31], and Per-XOR in protocol messages makes it almost impossible for an adversary (with RLC) to construct enough equations that may disclose the concealed secrets.On the other hand, RDC model is more powerful and requires an active attacker which can block the genuine authentication sessions (between the reader and the tags) and hence both the legitimate readers and the tag communicate with the previous pseudonyms and keys. The attacker then tries to find the differential relationship between the random nonce and finds conjecture secrets. However, RDC also fails to disclose the concealed secrets of nontriangular based UMAPs. This inventor of RLC and RDC also highlighted this inherent limitation of the models.The cryptanalysis proves that the EGP protocol is robust against all the attack models presented in Section3. None of the previous UMAPs (discussed here) can withstand all types of existing adversarial models discussed in the security analysis model which make them unsuitable for real world applications. On the other, the evaluation of EGP protocol based on robustness, reliability, and security proves that the presented authentication protocol is most suitable for the authentication of resource constraint IoT network perception layer.


## 4.1. Working of the EGP Protocol

Figure16 shows the detailed working of the protocol. The EGP protocol involves three main components: Tag (T), Reader (R), and the backend database D. Each ′T′ contains the one static secret ID; two sets of IDS and keys (Old and new). To avoid the possible desynchronization attacks, the ′R′ uses the buffer-based security framework proposed in [46]. In the buffer-based security framework, the reader maintains a dynamic memory architecture and stores all previous pseudonyms and keys (depending upon buffer size). To avoid buffer overflow, a RTC (Real Time Clock) has also been integrated at the reader side that manages the storage of variable. The basic symbols and notations used in this protocol are presented in Table 13.Table 13
Notations used in EGP.
Symbol Meaning P x ( a , b ) Per-XORb with a  P x - 1 ( a , b ) Inverse Per-XORb with a  ⨁ XOR  ∥ Concatenation  K Key  ′R′ Reader  ′T′ TagFigure 16
Block diagram of EGP protocol.The specifications of the protocol are as follows:(1)
The ′R′ initiates the protocol session by sending “hello” message towards the ′T′.(2)
Upon receiving of this query, the ′T′ responds with its current IDS.(3)
The ′R′ looks for the received IDS in its database and if a match occurs then it computes A,B, and C messages and sends to the reader. Otherwise, it will send another “hello” towards ′T′ and repeat the same process of finding matched entry. If the ′R′ does not find the matched entry in this second round, it will terminate the protocol session.(4)
On receiving ofA,B, and C messages, the ′T′ performs following three tasks:
(a)
Extract random nonce(n1,n2) from messages A&B:(99)n1=Px-1A,K(100)n2=Px-1B,K⊕n1(5)
Compute the local value ofC and compare it with the received C. If both of the values coincide, only then the ′T′ authenticates ′R′; otherwise it will terminate the protocol session with the particular ′R′. After successful authentication, the ′T′ computes the message D and transmits towards ′R′.(6)
UpdateIDS and key (Knext).(7)
Upon receiving of messageD, the ′R′ computes a local value ofD and compares it with the received one. If both values coincide then the ′R′ authenticates ′T′ and updates IDS andkey for the particular ′T′ in its database for future correspondence.Figure16 presents the block diagram of the EGP protocol.


## 4.2. Security Analysis of EGP Protocol

We analyze the security of the proposed protocol in two aspects: formal verification and resistance of the protocol against rudimentary attacks. The detailed description of the security analysis is presented as follows.


### 4.2.1. Formal Security Analysis

For formal security verification, we use GNY logic. The formal analysis tool uses abstract language and verifies the assumptions and objectives of the security algorithms. The detailed description of the analysis is as follows.(1) GNY Logic Analysis.GNY (Gong–Needham–Yahalom) logic is a mathematical formal verification tool that verifies the security assumptions and goals of security algorithms. The GNY logic is a multistep process which first translates the assumptions and public messages in abstract language and then starts validating goals. For validation of the goals, the GNY logic uses three rules: Being Informed, Possession, and Freshness Rules.(a)
Being Informed Rules. Any formula that M receives is considered as “being informed”.I1: if M is informed the formula N, which he did not convey in this run, then M is informed N(101)I1:M⊲*NM⊲NI2: if M is informed an encrypted formula with symmetric key (K) then M is informed the formula.(102)I2:M⊲NK,M∋NM⊲N(b)
Possession Rules. If M possesses a formula then it can possess other associated formulae as well.P1: M can possess any variable which is being informed(103)P1:M⊲NM∋NP2: if M possess two different formulae then it can possess their concatenation and functions as well.(104)P2:M∋N,M∋OM∋N,O,M∋FN,OTable 14 enlists the notations used in GNY logic analysis.(c)
Freshness Rules. On the basis of belief, M determines the freshness of messages.F1: if M believes that a formula is fresh then he also believes that any concatenation and function will be fresh.(105)F1:M≡#NM≡#N,O,M≡#FN,OTable 14
Notations used in GNY logic analysis.
S.No. Statement/Notations Interpretation 1 M Manager/Administrator  2 N Message/variable  3 R Reader  4 T Tag  5 I S Intermediate Step  6 M ⊲ ∗ N M is informed N, M didn’t convey in current session  7 M⊲N M is informed N  8 ( N ∥ O ) Concatenation ofN&O  9 M | ≡ # ( N ) M believes that Nis fresh  10 M | ≡ φ ( N ) M believes that Nis computable/recognizable  11 M | ≡ N M believes that N holds  12 M | ≡ M ↔ K Z M believes that Kis an appropriate secret for Z  13 M ∋ N M can possess N  14 M | ~ N M once conveyed N  15 N K Nis encrypted using symmetric key K(2) Formal Proof of EGP Using GNY Logic.The first step in GNY analysis is to describe the assumptions of the protocols which are followed by the formalization of the exchanged messages. Finally, the goals of the protocols are verified using formal analysis postulates.The authentication process mainly depends upon the pseudorandom numbers; therefore we apply analysis on first two messages only.The messages can be formulated as follows:(106)T⊲∗n1K~>R≡T↔KRT⊲∗n2n1,K~>R≡T↔n1,KRThe goal of sending such messages is(107)G1:T≡R∋n1,n2By applying the verification postulates, we can validate EGP’s goal as follows:(108)T⊲∗n1K~>R≡T↔KRIS1:T⊲*n1KSinceR≡T↔KRisalreadyassumedtobesatisfiedBy consideringI1,S4, and I2 we can have(109)IS2:T⊲n1KIS2:T⊲n1According to ruleP1, we get(110)IS3:T∋n1Now for second message as we know,(111)T⊲∗n2n1,K~>R≡T↔n1,KRIS4:T⊲*n2n1,KSinceIS3andR≡T↔KRisalreadyassumedtobesatisfiedIf we considerI1,S4, and I2 then IS4 can be represented as(112)IS5:T⊲n2n1,KIS6:T⊲n2FurtherIS6 can be interpreted as(113)IS7:T∋n2Hence fromIS3 and IS7, it can be observed that EGP optimally achieves its goal:(114)T≡R∋n1,n2If adversary tries to modifyn1, then effect of this alteration directly transfers to n2 as well. The tag will not verify message C, hence abort such protocol sessions, and will remain synchronized.


## 4.2.1. Formal Security Analysis

For formal security verification, we use GNY logic. The formal analysis tool uses abstract language and verifies the assumptions and objectives of the security algorithms. The detailed description of the analysis is as follows.(1) GNY Logic Analysis.GNY (Gong–Needham–Yahalom) logic is a mathematical formal verification tool that verifies the security assumptions and goals of security algorithms. The GNY logic is a multistep process which first translates the assumptions and public messages in abstract language and then starts validating goals. For validation of the goals, the GNY logic uses three rules: Being Informed, Possession, and Freshness Rules.(a)
Being Informed Rules. Any formula that M receives is considered as “being informed”.I1: if M is informed the formula N, which he did not convey in this run, then M is informed N(101)I1:M⊲*NM⊲NI2: if M is informed an encrypted formula with symmetric key (K) then M is informed the formula.(102)I2:M⊲NK,M∋NM⊲N(b)
Possession Rules. If M possesses a formula then it can possess other associated formulae as well.P1: M can possess any variable which is being informed(103)P1:M⊲NM∋NP2: if M possess two different formulae then it can possess their concatenation and functions as well.(104)P2:M∋N,M∋OM∋N,O,M∋FN,OTable 14 enlists the notations used in GNY logic analysis.(c)
Freshness Rules. On the basis of belief, M determines the freshness of messages.F1: if M believes that a formula is fresh then he also believes that any concatenation and function will be fresh.(105)F1:M≡#NM≡#N,O,M≡#FN,OTable 14
Notations used in GNY logic analysis.
S.No. Statement/Notations Interpretation 1 M Manager/Administrator  2 N Message/variable  3 R Reader  4 T Tag  5 I S Intermediate Step  6 M ⊲ ∗ N M is informed N, M didn’t convey in current session  7 M⊲N M is informed N  8 ( N ∥ O ) Concatenation ofN&O  9 M | ≡ # ( N ) M believes that Nis fresh  10 M | ≡ φ ( N ) M believes that Nis computable/recognizable  11 M | ≡ N M believes that N holds  12 M | ≡ M ↔ K Z M believes that Kis an appropriate secret for Z  13 M ∋ N M can possess N  14 M | ~ N M once conveyed N  15 N K Nis encrypted using symmetric key K(2) Formal Proof of EGP Using GNY Logic.The first step in GNY analysis is to describe the assumptions of the protocols which are followed by the formalization of the exchanged messages. Finally, the goals of the protocols are verified using formal analysis postulates.The authentication process mainly depends upon the pseudorandom numbers; therefore we apply analysis on first two messages only.The messages can be formulated as follows:(106)T⊲∗n1K~>R≡T↔KRT⊲∗n2n1,K~>R≡T↔n1,KRThe goal of sending such messages is(107)G1:T≡R∋n1,n2By applying the verification postulates, we can validate EGP’s goal as follows:(108)T⊲∗n1K~>R≡T↔KRIS1:T⊲*n1KSinceR≡T↔KRisalreadyassumedtobesatisfiedBy consideringI1,S4, and I2 we can have(109)IS2:T⊲n1KIS2:T⊲n1According to ruleP1, we get(110)IS3:T∋n1Now for second message as we know,(111)T⊲∗n2n1,K~>R≡T↔n1,KRIS4:T⊲*n2n1,KSinceIS3andR≡T↔KRisalreadyassumedtobesatisfiedIf we considerI1,S4, and I2 then IS4 can be represented as(112)IS5:T⊲n2n1,KIS6:T⊲n2FurtherIS6 can be interpreted as(113)IS7:T∋n2Hence fromIS3 and IS7, it can be observed that EGP optimally achieves its goal:(114)T≡R∋n1,n2If adversary tries to modifyn1, then effect of this alteration directly transfers to n2 as well. The tag will not verify message C, hence abort such protocol sessions, and will remain synchronized.


## 4.3. Desynchronization Attack

The desynchronization attacks presented in [34] force the legitimate readers and the tags to update different pair of pseudonyms and keys and therefore make the resources unavailable for the legitimate parties. To avoid such availability and desynchronization attacks, the EGP protocol uses dynamic memory architecture at the reader’s side. This memory architecture involves RTC (Real Time Clock) and Shift Registers to store the current and previous values of pseudonyms and keys of each associated tag. The memory architecture is located at the reader’s side and therefore does not increase the cost of the tag. If the adversary tries to block some genuine authentication sessions and uses replay attack models to desynchronize the EGP’ tag and the reader then this will be impossible for the adversary, since the reader keeps the records of n authentication sessions. The size of dynamic variable buffer at the reader’s side primarily depends on the architecture of the database associated with the network. The increase in buffer size enhances the synchronization of the tag/reader pair at the cost of increased memory requirement at the reader’s side.


## 4.4. Traceability Attack

In EGP if an adversary tries to find the conjunctureID through publically disclosed messages then because of optimal messages structure, she will get only ambiguous equation:(115)ID=Px-1D,Px-1C,K⊕px-1B,K⊕Px-1A,KBy keeping in view of computational complexity of (115), it will be almost impossible for an adversary to track the individual tag by resolving this equation. Moreover, most of the variables involved in EGP will get update after each authentication session; therefore EGP proves to be secure against all existing traceability attack models.


## 4.5. Full Disclosure Attack

The full disclosure attacks exploit the inherent weaknesses of theT-functions. The attackers usually perform different computational operations on public messages and try to obtain conjecture secret values. However, the inclusion of nontriangular primitive Per-XOR and inversePer-XOR makes EGP protocol almost impossible to retrieve the concealed secret from public messages. The protocol’s performance to unstructured and structured full disclosure attack is described as follows:(A)
Ad Hoc Attack. The ad hoc attacks target the lack of randomness in public messages and the linear behavior of the protocol’s primitives. In EGP protocol, the structure of the public messages is designed to avoid the previously presented unstructured full disclosure attacks. Every public message increments the degree of randomness by one; i.e., message A consists of random number n1, message B consists of n2 and n1, and message C consists of K∗,n2, and n1. Even if the adversary keeps the dynamic variables constant for multiple sessions by blocking the message D, the values of n1,n2, and K∗ change for every session and hence the values of public messages vary making it theoretically impossible to derive the tag’s ID by just eavesdropping the authentication sessions.In addition to this, thePer-XOR operator provides improved confusion and diffusion services to the public messages due to the following features:
(1)
TheXor operation masks the result of permutation making it impossible to reveal the LSB or MSB of the first operand of Per-Xor function without complete information of the second operand.(2)
The operands of thePer-Xor function in the EGP protocol are the irreversible combination of dynamic variables. The analysis of message D(Px(K∗⊕ID⊕n1,n2)) shows that even if the adversary obtains K∗⊕ID⊕n1 by exploiting the reversable nature of Per-Xor, the ID cannot be retrieved without the knowledge of K∗ and n1. This enables the presented primitive to effectively conceal the secret values associated with the session in public messages.In [45], an ad hoc full disclosure attack on the RAPP protocol is presented. In the proposed attack, the dynamic variables are kept constant by blocking the last message from the R to the T and then the weakness of permutation primitive is exploited to obtain the random number n1that eventually leads to disclosure of the tag’s ID. For the estimation of single random number, the adversary generates a database of two public messages consisting of constants IDS, K1,K2, and K3.In EGP protocol, the dynamic variables on the tag’s side can be kept constant by blocking messageD from the T to the R. This leaves the adversary with only three public messages (A,B,C) based on constant IDS and K. Since the EGP protocol uses two random numbers (n1,n2), the number of public messages is not sufficient to estimate the private keys generated by the R.Therefore, due to nonlinear behavior ofPer-Xor function and small number of public messages, the ad hoc attacks proposed for RAPP protocol are not applicable to the EGP protocol.(B)
Tango Attack. The tango attack proves to be unsuccessful against nontriangular based UMAPs. The inventors of the tango attack also highlighted this inherent weakness of the attack model. In EGP, we have extensively used nontriangular primitives (Per-XOR and InversePer-XOR) in its design, which requires extensive computational complexity O(8×2K×log2K!×log2n1!×log⁡(n2!) to retrieve ID. Therefore, it is almost impossible for an adversary to find the optimal GA equations and apply tango attack model on EGP.(C)
Recursive Linear and Differential Cryptanalysis. The RLC model exploits the weak diffusion properties of the protocols and uses the public messages to construct the set of linear equations for each individual bit of the concealed secrets. After constructing the sufficient equations, the adversary solves the equations recursively and tries to get the concealed secrets bit by bit. However, the incorporation of (optimal) nontriangular primitives such as recursive hash [41], Psuedo-Kasami codes [31], and Per-XOR in protocol messages makes it almost impossible for an adversary (with RLC) to construct enough equations that may disclose the concealed secrets.On the other hand, RDC model is more powerful and requires an active attacker which can block the genuine authentication sessions (between the reader and the tags) and hence both the legitimate readers and the tag communicate with the previous pseudonyms and keys. The attacker then tries to find the differential relationship between the random nonce and finds conjecture secrets. However, RDC also fails to disclose the concealed secrets of nontriangular based UMAPs. This inventor of RLC and RDC also highlighted this inherent limitation of the models.The cryptanalysis proves that the EGP protocol is robust against all the attack models presented in Section3. None of the previous UMAPs (discussed here) can withstand all types of existing adversarial models discussed in the security analysis model which make them unsuitable for real world applications. On the other, the evaluation of EGP protocol based on robustness, reliability, and security proves that the presented authentication protocol is most suitable for the authentication of resource constraint IoT network perception layer.


## 5. Conclusion

The 5th generation mobile communication systems are envisioned to offer high-speed broadband service which is a key enabling factor for the development in the field of the IoT networks. The security and privacy of the IoT network are of utmost concern since a large amount of user-specific data is being generated on a real-time basis. The identity verification of the communicating parties is a primary part of the secure perception layer. The resource constraint IoT networks use ultralightweight protocols for the node authentication. This paper presents a brief survey on the existing UMAPs and their cryptanalysis models. The UMAPs can be broadly classified into three categories based on the primitives used for the challenge/response message calculation, i.e., UMAPs with triangular functions, UMAPs with single nontriangular function, and UMAP with hybrid nontriangular functions. The hybrid nontriangular functions provide enhanced confidentiality, integrity, availability, and authentication (CIAA) services at the cost of increased gate equivalents. However, the literature review shows that almost all the existing UMAPs are vulnerable to multiple cryptanalysis attacks, i.e., desynchronization attack, full disclosure attack, and traceability attacks. In this paper, we have proposed a new ultralightweight authentication protocol named EGP (Extremely Good Privacy) for IoTs. The proposed protocol introduced a new ultralightweight primitive, Per-XOR which is composed of two extremely lightweight operations: XOR and permutation. This newly proposed primitive increases the confusion and diffusion properties of the public messages optimally and avoids all the existing adversarial models. The performance comparison of the EGP protocol shows that it outperforms compared to its contending UMAPs in terms of security. This remarkable feature makes EGP the best choice for extremely low-cost IoTs sensors and RFID tags.



---

*Source: 3295616-2019-07-21.xml*