Object Authentication Using RFID Technology: A Multi-tag Approach

Published Online March 2015 in MECS DOI: 10.5815/ijcnis.2015.04.06

In RFID technology, a small chip (RFID tag) contains identification information of an object and this information is read by the RFID reader in order to identify the object. Hence, this technology is useful in many real life applications. For example, the items in a shopping mall can be attached with RFID tag and be identified with the help of RFID reader. However, an unauthorized person can access the tag attached to an item and decrease the cost of the item. Therefore, authentication is an important requirement for the applications based on RFID technology[1][2]. Traditionally, the objects are attached with single RFID tag. However, the position of the object where the tag is attached may not be detectable by the reader whereas some other positions of the same object are detectable. Therefore, the detection probability of an object in this arrangement is less [3]. The detection probability of the object can be increased using multiple number of tags [3]. The tags are attached in such a way that if any part of the object is within the communication range of the reader, there is at least one tag attached to the object that is within the communication range of the reader. Thus the detection probability of the object increases [3]. Many security issues are involved in RFID technology such as eavesdropping, location privacy etc.[4] However, classical cryptography techniques are not applicable to this environment since the RFID tag has low resources in terms of computation, communication and storage. Hence we require lightweight cryptography primitives to make a balance between security and resource requirement. The researchers in earlier authentication schemes concentrated on the balance between security and resource optimization. However, these schemes cannot be extended to multi-tag environment since they use single set of security information for an object. If the same information is copied to multiple tags attached to the object, the adversary can easily compromise all the tags by compromising any one tag attached to the object. This motivates to do further research in this area.

The research questions that have been addressed in this paper are: 1) Whether multiple resources can be utilized to enhance the security. 2) Whether it is possible to prevent possible attacks during the authentication process. 3) Whether it is possible to implement the authentication task amid the resource limitations. The objective of this paper is to design an authentication scheme in multi-tag environment which can make a balance between the security and resource requirement. In addition to this, we have to find any benefit of multiple number of tags in an object. This paper proposes a lightweight authentication scheme assuming the objects are attached with multiple number of RFID tags. The proposed scheme utilizes multiple number of tags to increase the difficulty for the adversary and it can prevent most of the attacks. Proper analysis has been carried out to evaluate the security and resource requirements of the proposed scheme. Rest of the paper is organized as follows. In Section II, we have analyzed a few existing authentication schemes [5][6][11][12][14]. Section III describes the proposed authentication scheme. In Section IV, we have analyzed the proposed authentication scheme and then we have concluded in Section V.

• II.    Related Works

Many authentication schemes exist in the literature. However, the existing schemes consider single RFID tag for each object. In this section, we revisit a few their limitations. authentication schemes [5][6][11][12][14] and analyze

Fig. 1. Communication model

The scheme proposed by Weis et al.[5] is a hash function bashed authentication scheme. This scheme is vulnerable to many attacks like traceability, replay attack, etc. The modified version of this scheme called randomized hash-lock scheme [5] resolves the location privacy problem. However, it cannot prevent other kinds of attacks. Other hash function based authentication schemes are presented in [6][7][8][9][10]. Since these schemes use hash function, the tag efficiency is low. Guo Rui Li et al. [11] proposed an authentication scheme based on public key cryptography that can prevent many attacks. However, the use of public key cryptography makes their scheme computationally infeasible on RFID platform. Kim and Jun [12] proposed a lightweight mutual authentication protocol. The limitation in their scheme is that it can detect any attack at the last phase of the authentication process which costs unnecessary computations before the detection. Song and Mitchell [12] have proposed an authentication scheme which suffers from high computation overhead due to hash and MAC operations. Some attacks against this scheme are also reported in [13].

According to the research findings in [3], the attachment of multiple number of tags to an object helps to increase the detection probability of the object. However, to the best of our knowledge, any authentication scheme based on this multi-tag concept has not yet been reported in the literature. Our work in [14] focuses the multi-tag concept. In this protocol, at least the threshold number of tags attached to an object which were authenticated successfully in a particular session needs to be visible to the reader in order to successful authentication of the object in the next session. The proposed scheme in this paper although used multiple tags in an object, it does not have this limitation. In addition to this, a proper analysis of the improved scheme has been carried out which were missing in [14].

• III.    Proposed Scheme Using Multi-tag RFID System

We propose an efficient authentication scheme in this paper which assumes that every object is attached with multiple number of tags. Before describing the proposed scheme we describe the Communication Model and the Threat Model. Table 1 lists the meaning of symbols used in the following discussions.

Table 1. Meaning Of Symbols

Symbol	Meaning
G j	An object
m	Number of tags attached to an object
T i	ith tag in an object
IN i	Index value
S i	Secret key
TID i	Tag id in tag memory
N i	Session key in tag memory
TID i,old	Old tag id in backend server
TIB; i,new	New tag id in backend server
N i,old	Old session key in backend server
N i,new	New session key in backend server
U i	Update status
V, g i , g i ’	Random numbers
Valid j	Validity information for G j

A. Communication Model

The components involved in the communication model are a set of objects, RFID reader and a trusted server called backend server. Every object is attached with m number of RFID tags in a process similar to [3]. A workstation acts as the backend server which has relatively higher storage capacity. It keeps the information of the objects. A RFID reader acts as an intermediary between the tags attached to the objects and the backend server. The communication between the reader and the backend server is wired or wireless and is assumed to be secured. On the other hand, the communication between the reader and the tags attached to the objects are wireless and is not secure. Fig. 1 illustrates this communication model.

• B.    Threat Model

He adversaries may utilize the insecure medium between the reader and the tags attached to the objects. Following are the possible attacks which can be mounted during the authentication process.

Passive attacks: The adversary A silently extracts secret information about the legitimate objects.

• -    Eavesdropping:   A silently listens to the

communication and tries to extract the secret information such as identifier, session key, secret key, etc.

• -    Location privacy: A tries to find out a pattern from the requests and responses, and tries to trace the object.

• -    Location privacy between two successful sessions: Between two consecutive successful sessions, A can try to trace an object.

Active attacks: The adversary not only listens to the vital information but also tries to disrupt the authentication process. Any adversary may mount the following active attacks:

• -    Man-in-the-middle attack: A may modify the information communicated through insecure medium and thus can disrupt the authentication process.

• -    Replay attack: The authentication information of a legitimate session may be saved and replayed for successful validation in later sessions.

• -    Forward secrecy and Backward secrecy: Compromising the secret information used in one valid session, A may try to obtain the secret information to be used in later or previous sessions.

• -    De-synchronization attack: In some situations, the information such as identifier, session key etc. for an object are updated and then communicated from either reader to object or object to reader in each successful session. However, if an adversary blocks the updated information then there can be a synchronization problem between backend server and the object.

• -    Impersonation attack: A may clone a legitimate tag and use the cloned tag to impersonate the legitimate tag.

• C.    Proposed protocol

The proposed authentication scheme has two phases, namely, Setup phase and Authentication phase. Fig. 3 illustrates these phases. Before introducing these phases, we describe the information maintained by the components mentioned in the communication model.

Information in Backend Server and Tags: The tag attached to an object contains the information about the object. It contains the index value IN_i , secret key S_i , tag identifier TID_i and session key N_i .

I IN i и Si □ TID i 1   N i

The backend server contains a database to keep the information for all the objects. One record in the database contains the information about one object. This record contains a validity information valid j and the information for m number of tags attached to the corresponding object.

The record for an object is divided into m number of sub-records. Each sub-record contains index value IN_i , secret key S i , two tag identifiers TID i,old , TID i,new , two session keys N i,old , N i,new , update status U i and random number information g i ’ . Fig. 2 illustrates the record for an object kept in the backend server.

Fig. 2: Information in backend server

Setup phase: In Setup phase, the tags and the backend server are initialized and deployed for authentication process to be performed in future. We consider n objects. In the illustration, we describe the initialization process for the object G j, 1 ≤ j ≤ n.

• -    G j is assigned the tags T_i,, i = 1, 2, …, m . The memory of each tag T_i is loaded with an index value IN_i (Index values are unique corresponding to the tags attached to an object. However, any two or more objects have the tags with same index value.), a secret key S i , a tag id TID i and a session key N i .

• -    The Valid j field in the record for G j is initialized to zero. The sub-records for the tags attached to G j are initialized as follows. The index value IN_i and secret key S_i which were loaded to the memory of the tag T_i are also loaded to the corresponding fields. The tag id TID i which was loaded to the memory of tag T i are also loaded to both the fields TID i, old and TID i, new . Similarly, the session key N i which was loaded to the memory of the tag T i are also loaded to both the fields N i, old and N i, new .

Thus, after initialization process, the assigned tags are attached to the corresponding objects appropriately similar to the process described in [1] and the objects are deployed.

Authentication phase: In authentication phase, the objects are authenticated as and when required. We use separate algorithms for the components mentioned in the communication model (described in Section III.A). Algorithms 1, 2, 3 are performed by the reader, the tags attached to an object and the backend server respectively.

Brief description: During authentication phase, the backend server generates a random number v and sends it to the reader. The reader broadcasts this v. The tags within the communication range of the reader receive this v and replies with authentication information Ki along with random number gi and index value INi. Reader receives the responses from the tags and forwards these to the backend server. The backend server receives each set of response INi, Ki, gi and verifies the validity. It starts with the first record kept in the database and uses the sub- record under this record having index INi. It verifies Ki using the new identifier and session key and on successful verification, it makes the corresponding update flag Ui as 1. If verification is not successful using new information, it uses old identifier and session key to verify Ki. This time it makes the update flag Ui as 2. It also increases validj by 1 on successful verification using either new or old information. If the verification fails using both new and old information, it selects the next record and continues this until it finds a valid record or finishes with all records in the database.

Object		Reader	Backend Server
Setup phase
in„ st. ж. л; г = 1,2,,,,. in			IN., Si, TID.m, TID.^.NiM.N.,^ U,^^ i = 1,2, м.,т, Validj 4- 0
4ut/ienricafton phase
к.^т-даф^®^-^ Extracts Ж-,ЛГ. from Ph.Pg, If Pi, is valid Updates TIDt+- TIDIN’, ^N*	3. IN^K^g,	1. и t------- A DLK,.^	Generates v Verifies K. with дл record under index IN, If verified on TIDi, NiiBew Validj <- Validj + l,l/j 4- l,g' e- g, Else if ver ified on TID^oU.N^m Validj <— Validj +1. Lj 4— 2, g' <~ g, If Valid, >l,j = l,2,...,n If L'; = l.i - 1.2m Generates Т11У,, N- randomly Generates Р-.р-.Рц using TID, ^w, ^.ЖЗ'.д',. ™,,oii i- TIDx,new'^ i,dd t- Niincw tid^-tid-.n^^n; Else If ['j = 2 Generates TID^.N- randomly Generates Рц.Р-.Рц using TID-^ N^TIDVNV^ TID^w-TlP,Ni.M^N\ Else ignores and stops.
	6. IN-.Pi.KPh 4-------------------------	5. PVi.Pn.Psi.Psi i--------------------------------

Fig. 3: Proposed authentication protocol

Algorithm 1 executed by reader

• 1:    Receives v from backend server and broadcasts

• 2:    Receives computed information IN_i, K_i, g_i from tags

• 3:    Forwards IN_i, K_i, g_i to backend server

• 4:    Receives computed information IN_i, P_1i, P_2i, P_3i from backend server

• 5:    Forwards IN_i, P_1i, P_2i, P_3i to tags

Thus the backend server verifies all the responses. It then identifies the valid object. To do this, it searches the records with valid j greater than or equal to the threshold value l . If it finds any such record, it identifies the corresponding object and generates the update information P_1i, P_2i, P_3i for the tags T_i attached to the same object for which the U_i is a nonzero value. If the value of U_i is 1, it uses the new identifier TID_i,new and

Algorithm 2 executed by a tag attached to an object

• 1:    Receives random number v

• 2:    Generates g_i randomly and then computes

K i ← ( TID i - g i ) ⊕ (( v ⊕ g i ) - N i )

• 3:    Sends IN_i, K_i, g_i to reader

• 4:    Receives IN_i, P_1i, P_2i, P_3i from reader

• 5:    If IN_i = own index then

• 6:    TID i ′ ← (( P 1 i ⊕ (( TID ⊕ v ) - S i )) - S i ) ⊕ g i ,

N i ′ ← (( P 2 i ⊕ (( N i ⊕ g i ) - S i )) - S i ) ⊕ v

• 7:   If P = (( S ⊕ v ) - ( P ⊕ TID ′ ⊕ N )) ⊕ (( P ⊕ TID

⊕ N ′ ) - ( S ⊕ v ) then

8:     Updates TID ←TID',N ←N'

session key N_i,new to generate the update information. Otherwise, it generates the update information using the old identifier TID i,old and session key N i,old . After completing the updation process, it resets the valid flags valid j of all the objects and update flags U i of all the tags kept in the database. The backend server sends IN i , P 1i , P_2i and P_3i to tags via reader. The tag receives this

Algorithm 3 executed by backend server

We analyze the proposed scheme to evaluate its applicability in practical scenarios. We choose four parameters,     namely,     security,     computation, communication and storage requirements.

• A. Security Analysis

The communication between tag and the reader can be misused by the adversaries who may try to mount various attacks. Therefore the proposed scheme needs to be secure against these attacks. We analyze the security of the proposed scheme in this section.

Informal Security Analysis: We informally analyze how an adversary A can mount various attacks mentioned in the threat model and how the proposed scheme can prevent these attacks.

• -    Eavesdropping: A can intercept g i , v, K i , P 1i , P 2i , P 3i and try to find out the secret information such as secret key S i , session key N i , etc. For example, he may try to compute TID_i from K_i . He needs to separate ( TID_i - g_i ) and (( v ⊕ g_i ) - N )) from K_i and then can compute TID_i from ( TID_i - g_i ). However, Shannon has proved in [15] that it is not possible to separate A and B from A ⊕ B as long as the bit size of A and B are same and any of A or B does not contain a value which it had contained in any other session completed earlier¹. Since the size of ( TID_i -g i ) and (( v ⊕ g i ) - N )) are same and they are not same in multiple sessions, A is unable to separate these from K i . Similarly, the other equations are secure from eavesdropping.

• -    Location privacy: A can try to find out a pattern using the information g i , v, K i , P 1i , P 2i , P 3i in multiple sessions. The proposed scheme uses new random numbers in each session to generate g_i, v, K_i, etc. For example, K_i consists of randomly generated g_i and v which were not used in the previous sessions. Therefore the adversary cannot relate the K i of one session with the K i of other sessions. Similarly, he cannot use other information transmitted through the insecure medium to find a pattern. He can try to use the index information to trace an object. However, there can be the responses with same index information from more than one object.

• -    Location privacy between two successful sessions: During the time between two successful sessions, A can try to replay same v and can expect same response K i from the tag. However, the tag randomly generates g_i and includes it into K_i . Therefore, the responses are not same and A cannot trace the object. In similar argument, he cannot trace the object intercepting the information P_1i, P_2i, P_3i .

  information and updates its memory after verifying the received information.

  
  

  IV. Analysis of the Proposed Scheme

  
  

  ¹ For i^th bit, C i = A i ⊕ B i . Let B i is a random bit. Hence for all i , P ( B i = 0 ) = P ( B i = 1 ) = 0.5 . Let P ( A i = 0 ) = p i . Therefore, P ( A i = 1 ) = 1 - p i . Now, P ( C i = 0 ) = P ( A i = 0 ) × P ( C i = 0 | A i = 0 ) + P ( A i = 1 ) × P ( C i = 0 | A i = 1 ) = P ( A i = 0 ) × P ( B i = 0 ) +P ( A i = 1 ) × P ( B i = 1 ) = pi × 0.5 + ( 1-p i ) ×0.5 = 0.5 . Therefore, P ( C i = 0 ) does not depend on p i . Conversely, we can say that the probability of obtaining correct A i from the given C i is 0.5, where B i is random.

  
  

• -    Man-in-the-middle attack: A can modify K i and expect that the modified information will be validated in the backend server. However, since he does not know the secret information, his modified information cannot be validated successfully. A can modify P_1i, P_2i and expect that the tag will extract the wrong information from P_1i, P_2i and update. However, since he does not know the secret information, he cannot generate a valid P_3i which can validate the modified P 1i and P 2i . The tag will use this P 3i to verify the authentication and integrity of P 1i and P 2i , and will ignore the modified information.

• -    Replay attack: A can replay v used in the previous session and can expect that the tag will send the same response K_i . Since the tag uses a random number g_i as we have mentioned in the argument of location privacy during the time between two successful sessions, A cannot trace the object. He can replay the K i . However, the v used in this K i is not equal to the v generated in this session by the backend server. Therefore, the replayed information cannot be validated in the backend server. Similarly, the replayed P_1i, P_2i and P_3i cannot be validated in the tag due to new g_i and v .

• -    Forward secrecy: Suppose A captures TID i and try to compute TID i ’ . Since he does not know S i , he is unable to compute (( TID i Ф v ) - S i ) from P 1i and hence cannot compute TID i ’ . In similar argument, he cannot compute N i ’ using N i . If he is able to capture S i, then also he cannot compute TID i ’ or N i ’ since he does not know TID_i . If he is able to capture all S_i, N_i and TID_i , then only he can compute TID_i’ or N i ’.

• -    Backward secrecy: Similar to forward secrecy, the proposed scheme prevents the backward secrecy, i.e A can only be able to intercept S i , N i and TID i if he is able to capture all the secrets S i , TID i ’ and N i .

• -    De-synchronization attack: A tries to mount this attack as following:

• -    Blocks the update information P 1i , P_2i, P 3i and expects that the backend server has modified the session key and tag id, however, the tag has not updated the corresponding secrets and they cannot communicate in future. The proposed scheme keeps the old copy of the tag id and session key. Therefore, the response from the tag can be validated in backend server using the old information and this information is unchanged until the backend server finds that the tag has updated its information, i.e. the response from the tag has verified using new information.

• -    Modifies P 1i , P 2i and expects that the tag retrieves the wrong information and hence there will be a mismatch between the information in tag and the backend server. As we have explained in the Man-in-the-middle attack, the tag will update only if it verifies P 3i successfully which is the integrity information of P 1i , P 2i . Hence tampering of P_1i, P_2i will be detected and

the tag will not update the secrets. Therefore, the proposed scheme prevents the Desynchronization attack and the tag and the backend server can still be able to communicate further after this attack.

• -    Impersonation attack: A may physically clone a legitimate tag and use the cloned tag to impersonate the corresponding object. The proposed scheme uses a threshold value ( l ) to validate an object, i.e. A have to clone at least the threshold number of tags in order to impersonate an object. This will increase the difficulty for A to mount this attack. Thus the existence of multiple number tags in an object helps to increase the difficulty for the adversary. The proposed scheme has taken this advantage to increase the security during authentication.

Formal Security Analysis: In this section, we provide formal proofs which can assure the security of the proposed scheme. Firstly, we show that the adversary is unable to mount any attack by intercepting information transmitted through insecure medium during a particular session. Secondly, the adversary may try to intercept information transmitted during multiple sessions and try to mount attacks after manipulation of these information. We show that the proposed scheme is safe from this operation. Finally, we show that the adversary may try to approximate the addition or subtraction operation used in the equations for the information transmitted through insecure medium into XOR operation and try to mount attacks described in the threat model. We show that the probability of such attack in the proposed scheme is negligible.

Definition 1: ( Security of the Object Authentication Scheme ( OAS )). The OAS is secure if, any efficient adversary, given any one interaction (not necessarily complete) and a history of earlier interactions, cannot derive (with probability greater than 0.5 + θ , for a non-negligible θ ) any secret.

Problem 1: Find p and q from a given number n , where p, q are unknown random numbers of same length (bit size) and n = p ⊕ q .

Hardness of Problem 1: Let Adv ^XOR denotes an adversary A 's advantage in finding p and q from the given n , we have Adv XOR = Pr[( p , q ) ^_R A: p , q being random numbers of same length and n = p ⊕ q² ] . A is allowed to be probabilistic and the probability in the advantage is computed over the random choices made by A . We call the Problem 1 as computationally infeasible, if Adv XOR , for any sufficiently small G> 0 .

Theorem 1: The proposed object authentication scheme (OAS) is secure from intercepting the secret information by A under the experiment depicted in Algorithm 4.

Algorithm 4: EXP ^OAS 1

• 1:    Intercepts g i , v, K i , P 1i , P 2i , P 3i

• 2:    Calls Disclose on input K_i and obtains ( TID_i - g_i ), (( v ⊕ g i ) - N i ) ← Disclose( K i )

• 3:    Computes TID i ← ( TID i - g i ) + g i , N i ← - ((( v ⊕ g i ) - N i ) - ( v ⊕ g i ))

• 4:    Calls Disclose on input P_1i and obtains ( S_i + ( TID_i’ ⊕ g_i )), (( TID i ⊕ v ) - S i ) ← Disclose( P 1i )

• 5:    Computes S i ← - ((( TID i ⊕ v ) -S i ) - ( TID i ⊕ v )), TID i ’ ← ( S i + ( TID i ’ ⊕ g i )) - S i ) ⊕ g i

• 6:    Calls Disclose on input P_2i and obtains ( S_i + ( N_i’ ⊕ v )), (( N i ⊕ g i ’ ) - S i ) ← Disclose( P 2i )

• 7:    Computes N_i’ ← (( S_i + ( N_i’ ⊕ v )) - S_i ) ⊕ v

• 8:    If P 3i = (( S i ⊕ v ) - ( P 1i ⊕ TID i ’ ⊕ N i )) ⊕ (( P 2i ⊕ TID i

⊕ N_i ) - ( S_i ⊕ v )) then

• 9:    Successfully eavesdrop the secrets

• 10:    Else

• 11:   Return 0 (Failure)

Proof: A intercepts g i , v, K i , P 1i , P 2i , P 3i and tries to intercept the secret like session key, secret key, etc. using the experiment depicted in Algorithm 4. He calls a random oracle Disclose and finds the components tied with XOR operation. He then computes the secrets. However, the probability that he can separate the components tied with XOR operation depends on probability that he can solve the Problem 1. According to the hardness of the Problem 1, the probability of separating the components tied by XOR operation is sufficiently small. Therefore, the success probability of the experiment depicted in Algorithm 4 is sufficiently small and the proposed scheme is secure under this experiment.

Corollary 1: The proposed object authentication scheme is secure from the attacks described in the Threat model.

We define a random oracle Disclose.

Disclose: This random oracle unconditionally outputs p, q from the input n , where n = p ⊕ q .

Proof: Suppose, A intercepts the secret information such as session key, id, etc. using the experiment depicted in Algorithm 4. Since he has the secret information, he can mount the attacks like replay attack, man-in-the-middle attack, de-synchronization attack. He further intercepts the information communicated in the next session and tries to mount the attack against the location privacy using the experiment depicted in Algorithm 5. He can also get the confirmation about the attack against forward and backward secrecy from this experiment. However, the success probability of this experiment depends on the probability of intercepting the various secrets. Therefore the success probability of this experiment depends on the probability of success in the experiment depicted in Algorithm 4 which is sufficiently small.

Algorithm 5 : EXP ^OAS 2

• 1:    Intercepts g_i ¹, v ¹, K_i ¹, P ₁ ¹ _i , P ₂ ¹ _i , P ₃ ¹ _i

• 2:    If K i ¹ = ( TID i ′ - g i ¹ ) ⊕ (( v ¹ ⊕ g i ¹ ) - N i ′ ) then

• 3:    Tracing is successful

• 4:    Computes TID_i ′′ ← ( P ₁ ¹ _i ⊕ (( TID_i ′ ⊕ v ¹) - S_i ) - S_i ) ⊕ g_i ¹

• ^{5:    Computes} N ′′← ( P ¹ ⊕ (( N ′⊕ g ¹) - S ) - S ) ⊕ v ¹

• ^{6:    If} P ¹ = (( S ⊕ v ¹) - ( P ¹ ⊕ TID ′′⊕ N ′ )) ⊕ (( P ′ ⊕ TID ′⊕ N ′′ ) - ( S ⊕ v ¹)) ^then

• 7:    Breaking forward secrecy is successful

• Theorem 2:    The proposed object authentication scheme is secure from A under the experiment depicted in

Algorithm 6.

Algorithm 6 EXP ^OAS 3

• 1:    For each pair of equations in ℒ

• 2:    If the pair has common component then

• 3:    Apply XOR operation on the pair and obtain

• a new equation ℰ

• 4:    If ℰ ∉ ℒ then

• 5:   Add ℰ into ℒ

• 6:    End For

Equations in unsuccessful session Ses_i

Ki =(TIDi-gi)⊕((v⊕gi)-Ni)

P1i =(Si+(TIDi'⊕gi))⊕((TIDi⊕v)-Si)

P2i =(Si+(Ni'⊕v))⊕((Ni⊕gi)-Si)

P 3 i = (( Si ⊕ v ) - ( P 1 i ⊕ TIDi ^' ⊕ Ni )) ⊕

((P ⊕TID ⊕N')-(S ⊕v))

Equations in successful session Ses_i+1

Ki1 =(TIDi-gi1)⊕((v1⊕gi1)-Ni)

P11i =(Si+(TIDi'⊕gi1))⊕((TIDi⊕v1)-Si)

P21i =(Si+(Ni'⊕v1))⊕((Ni⊕gi1)-Si)

P ¹ = (( S ⊕ v ¹) - ( P ¹ ⊕ TID ^' ⊕ N )) ⊕

((P21i ⊕ TIDi ⊕Ni')-(Si ⊕v1))

Equations in successful session Ses_i+2

Proof: A can intercept the information transmitted in multiple sessions and perform XOR operation over the corresponding equations of the intercepted information. Thus he can obtain secret information and mount various attacks. In order to verify whether this attack is present or not, we perform the experiment depicted in Algorithm 6. We prepared a list of equations ℒwhich consists of the equations for the information transmitted in an unsuccessful session Ses_i , a successful session Ses_i+1 and another successful session Ses i+2 . These sessions are three consecutive sessions. We select the sessions in such a way that any other session cannot provide any extra benefit. The algorithm takes the list ℒas an input where each equation in the list has two components that are tied with XOR operation. For example, the equation for K_i consists of two components ( TID i - g i ) and (( v ⊕ g i ) - Ni) that are tied with XOR operation. If it finds any pair of equations which has a common component tied by XOR operation, it applies XOR operation over these two equations and outputs a new equation which is added to ℒ. It selects this pair to apply the XOR operation because the XOR operation will suppress the common component and hence the resultant equation may become vulnerable. However, if any pair does not have any common component, the XOR operation cannot help. The XOR operation will increase the components in the resultant equation and this cannot be benefited to A. Thus it continues till it obtains a new equation in ℒ. According to our experiment, there is no new equation produced by the Algorithm 6. Therefore the proposed scheme is secure.

XOR-approximation: Approximate a given equation A = ( B + C ) ⊕ ( D - E ) into another equation A’ = ( B ⊕ C ) ⊕ ( D ⊕ E ). The probability that A = A’ is ( 0.75 ) ^d-1 , where d is the length (bit size) of A, A’, B, C, D, E³ .

• Theorem 3:    The proposed object authentication scheme is secure from the attacks in the threat model under the XOR-approximation assumption.

Proof: The equations used in the proposed scheme consist of +/- operation and A can convert these equations using XOR approximation and then try to mount the attacks mentioned in the threat model. However, the success probability depends on the successful approximation. The probability of successful approximation is ( 0.75 ) ^d-1 , where d is the length (bit size) of each secure information. Table 2 shows this probability on various values of d . Clearly, the probability decreases with increase in d . However, a large d value is computationally infeasible. Therefore, an appropriate value of d needs to be chosen which can be computationally feasible and the success probability to mount various attacks is sufficiently small.

Table 2: Success probability on various d values

d	1	2	32	64	96	128
β	1	7.5	1.339366	1.345425	1.351512	1.357627
		× 2-3	× 2-13	× 2-27	× 2-40	× 2-53

Security Comparison: We Compare The Proposed Scheme With A Selected Set Of Existing Authentication Schemes. Table 3 Shows That The Proposed Scheme Satisfies All The Security Requirements Mentioned In The Threat Model Except The Impersonation Attack. However, The Use Of Multiple Number Of Tags In Each Object Helps To Increase The Difficulty For The Adversary To Mount This Attack. The Existing Schemes Are Unable To Prevent Two Or More Attacks.

Table 3: Security assurance

	a	b	c	d	e	f	g	h	i
Weis et al.[2]	N	Y	N	N	N	Y	Y	Y	N
Randomized hash[2]	N	Y	Y	Y	Y	Y	Y	Y	N
Song et al.[3]	Y	Y	Y	Y	Y	N	Y	Y	N
Hyung-Joo et al.[9]	Y	Y	N	Y	Y	Y	Y	Y	N
Guo-Rui Li et al. [8]	Y	N	Y	Y	Y	N	N	N	N
Dhal et al.[11]	Y	Y	Y	Y	N	Y	Y	N	P
Proposed scheme	Y	Y	Y	Y	Y	Y	Y	Y	P

a : Eavesdropping, b : Man-in-the-middle attack, c : Replay attack, d :Traceability, e : Traceability between two successful sessions, f: Forward security, g : Backward security, h : De-synchronization attack, i : Impersonation attack, Y : Satisfy, N: Not satisfy, P: Partially satisfy.

• B.    Computational Overhead

We analyze the computational overhead of the proposed scheme and compare the scheme with the existing schemes. Table 4 illustrates the computation requirements in various schemes. In our analysis, we consider the operations used in the proposed scheme such as XOR, addition, subtraction, random number generation, and the other operations used in the existing schemes such as hash functions, attachment/detachment operation, etc. Table 4 shows that the tag in the proposed scheme uses most number of XOR and addition, subtraction operation. However, these are elementary operations. It uses only one heavyweight operation, i.e. random number generation. However, the tags in the existing schemes [3][8][9] use many heavyweight operations. The schemes proposed in [2] use minimum operations. However, these schemes are unable to prevent most of the attacks. Similarly the backend server uses many elementary operations in the proposed scheme whereas in the existing schemes [3][8][9], it uses many heavyweight operations. The reader in the proposed scheme uses no operation in the proposed scheme whereas the schemes proposed in [3][8][9][11] use one or more heavyweight operations. Therefore, the proposed scheme is lightweight in respect to the computation overhead in tag and can be deployable in real life environment.

• C.    Communication Overhead

  Table 4: Number of operations performed in various scheme

  	Tag					Reader					Backend Server
  	a	b	c	d	e	a	b	c	d	e	a	b	c	d	e
  Weis et al.[2]	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
  Randomized hash[2]	0	0	1	1	1	0	0	1	1	0	0	0	0	0	0
  Song et al.[3]	6	0	6	3	1	0	0	0	0	1	4 n + 4	0	6	2n + 1	0
  Hyung-Joo et al.[9]	7	1	5	0	5	0	0	2	0	1	4 n + 4	n	n + 7	0	2 n + 2
  Guo-Rui Li et al. [8]	2	0	7	5	1	0	0	0	0	1	n + 1	0	4 n + 3	4n + 2	1
  Dhal et al.[11]	4 m + 3	2	0	0	0	0	0	0	1	1	mn + 6 m	2 nm	0	1	2 m + 1
  Proposed scheme	14	8	0	0	1	0	0	0	0	0	4 n 2 m + 13 m	6 n 2 m	+ 6 m 0	0	2 m + 1

  
  

We compute the overhead due to communication between the components mentioned in the communication model.

Table 5: Communication overhead of various scheme

	Tag	Reader	Backend server
Weis et al.[2]	4	6	2
Randomized hash[2]	4	6	2
Song et al.[3]	4	9	5
Hyung-Joo et al.[9]	5	9	4
Guo-Rui Li et al. [8]	6	5 + 6 n	3 n + 2
Dhal et al.[11]	3 m + 4	6 + 6 m + 2 mn	3 m + 4
Proposed scheme	4 m + 4	8 m + 6 mn + 2	4 m + 3 nm + 1

n : Number of objects, m : Number of tags attached to an object

Table 5 shows that the communication requirements for the existing schemes [2] [3][8][9] are less. However, the proposed scheme and the scheme in [11] require communicating more information due to the fact that multiple number of tags are present in each object. However, multi-tag arrangement helps to increase the difficulty for the adversary to mount attacks.

• D.    Storage Requirement

RFID tags have limited storage capacity. Therefore, we analyze the existing schemes and the proposed scheme in terms of storage requirements. Table 6 illustrates this analysis and it shows that the scheme proposed in this paper require storing 4 parameters. If we consider the maximum size of each parameter as 128 bits then the tag requires storing only 512 bits information. The tags in the existing schemes also require storing almost equal number of information bits. Though the backend server does not suffer from storage limitations, we analyze the storage requirement for these components as well. According to Table 6, the proposed scheme and the scheme in [11] require higher storage overhead in backend server. This is again due to the fact that each object is attached with multiple number of tags.

Table 6: Storage requirement

	Tag	Reader	Backend server
Weis et al.[2]	3	0	3 n
Randomized hash[2]	1	0	n
Song et al.[3]	1	0	5
Hyung-Joo et al.[9]	2	0	2 n
Guo-Rui Li et al. [8]	3	0	5 n
Dhal et al.[11]	5	0	4 mn
Proposed scheme	4	0	8 mn + n
n : Number of objects, m : Number of tags attached to an			object

• V. Conclusion

Authentication is a necessary task in RFID technology due to its pervasiveness. Existing authentication schemes assume the objects are attached with single tag. However use of multiple number of tags to an object can enhance the detection probability of the object. Our work has motivated from the multi-tag concept which uses multiple number of tags for each object to increase the difficulty for the adversary to mount various attacks. The proposed authentication scheme is lightweight and secure which is verified through proper analysis. However, due to the responses from multiple number of tags for each object, the traffic congestion between reader and object is high. Also a suitable Physical Unclonable function (PUF) can be used to prevent the impersonation attack which is missing in the proposed scheme.