is fixed. An adversary easily compromises mutual authentication by simply eavesdropping and replaying the sessions between tag and reader. So Hash-Lock protocol is vulnerable to spoofing attack and replay attack. Moreover, an adversary easily traces the tag’s holder by the tag’s identifier and its fixed pseudonym.
In order to overcome the flaws of Hash-Lock protocol, S. A. Weis and S. E. Sarma et al. proposed randomized Hash-Lock protocol  . This protocol uses a pseudorandom number generator (PRNG) to randomize the transferred sessions between tag and reader. Tags respond to reader’s queries by generating a random value r, then Hashing its and concatenating the result with r, and sending them to the reader. A legitimate reader identifies one of its tags by performing a brute-force search of its known. Then the reader sends the identified tag’s to the tag by plaintext. It is easy for an adversary to eavesdrop and obtain the identity of the tag. Hence, it is vulnerable to spoofing and replay attack. Moreover, the tag’s holder is easily traced and this protocol cannot satisfy forward security.
M. Ohkubo et al. firstly proposed Hash-chain protocol  . The aim of their protocol is to provide better protection for the user’s privacy by refreshing the identifier of the tag. Different from Hash-Lock protocol, Hash- chain protocol uses two different Hash functions, and. This protocol only provides one-way authentication, namely, the reader authenticates the tag while the tag does not authenticate the reader. To achieve forward security, this protocol uses Hash chain technique to renew the secret key stored in the tag. But this protocol does not use a random number generator and it is vulnerable to spoofing and replay attack. Ohkubo et al.’s scheme has a complexity in terms of Hash computations of, where m is the given maximum limit on Hash chain length and n is the total number of tags. Thus, when the number of tags or the chain length is large the computation becomes unimaginable for an RFID system. Another similar scheme was provided by Sang-Soo Yeo et al.  . The scheme gave a conceptually simple but elegant solution to defeat the tracing problem and to ensure forward security. This scheme requires each tag to support 2 Hash functions. When the tag is queried by a reader, it sends Hash value of its current identifier by using Hash function, , then renews its identity information by using another different Hash function,. These protocols use two different Hash functions and it is not suitable to the low-cost RFID tags.
Yong Ki Lee et. al. proposed a secure and low-cost authentication protocol for the RFID system, Semi-Rand- omized Access Control (SRAC)  . It also uses a pseudonym, , to replace the tag’s like Hash- Lock protocol. It provides mutual authentication and forward security. It can protect RFID systems from many attacks, such as tracing, cloning and denial of service. However, it is vulnerable to replay attack. The adversary can simply eavesdrop and reuse to be authenticated successfully. Later, Su Mi Lee et al. used the challenge-response mechanism and proposed a low-cost RFID authentication protocol (LCAP)  . The aim of their effort is to solve the de-synchronized problem by maintaining a previous identifier in the backend server. This protocol provides mutual authentication and guarantees the location privacy of the tag’s holder. It also provides untraceability by changing tag’s identification dynamically. Nevertheless, it does not provide forward security, namely, an adversary can infer previous sessions about the tags after it reveals the present secrecy of the tags.
Jung-Sik Cho et al.  proposed a new Hash-based authentication protocol to solve the secure and private problems for the RFID system. However, Hyunsung Kim  demonstrated that this protocol is vulnerable to DOS attack. He pointed out that Jung-Sik Cho et al.’s protocol is vulnerable to traffic analysis and tag/reader impersonation attack. More precisely, an adversary can impersonate a valid tag or reader with probability 1/4. Finally, an adversary can obtain some information about the secrecy of the tag in the next session with probability 3/4. Therefore Hyunsung Kim proposed an improved protocol to offer protection against the attacks described above. But this enhanced version is as insecure as its predecessor. Walid I. Khedr  pointed out that an adversary can perform a de-synchronization attack by intercepting and tampering the transferred messages between tag and reader. Further, Walid I. Khedr justified that Jung-Sik Cho et al.’s protocol cannot ensure forward security. Masoumeh Safkhani and Pedro Peris-Lopez et al.  also constructed three different attacks to demonstrate Jung-Sik Cho et al.’s protocol is vulnerable to de-synchronization attack and tag/reader impersonation attack. Masoumeh Safkhani and Pedro Peris-Lopez et al. justified that the de-synchronization attack succeeds with probability 1 and the complexity of the attack is only one run of the protocol.
J. H. Ha and S. J. Moon et al.  proposed a Hash-based RFID security protocol and proved that their protocol can provide forward privacy. However, Da-Zhi Sun and Ji-Dong Zhong  pointed out that an attacker can track a target tag by observing previous unsuccessful sessions. Da-Zhi Sun et al. justified that J. H. Ha et. al.’s protocol fails to provide forward privacy as they claimed. Then they proposed another Hash-based authentication functions to overcome the weaknesses of J. H. Ha et al.’s protocol. But all these protocols use two different Hash functions. They require more computing and storage cost. They are not suitable for the low-cost RFID system.
Liu Yang, Peng Yu et al.  proposed an RFID secure authentication protocol based on Hash function. Their protocol ensures the privacy of the tag’s secret information and realizes three party mutual authentications among tag, reader and backend server. But, for each authenticating process of the protocol, the tag and the reader call Hash function more than five times respectively. So their proposed protocol is so complicated that it is not suitable to the low-cost RFID system.
Győző Gódor and Sándor Imre  analyzed the typical Hash-based authentication protocols as described above. Then they proposed a Hash-based mutual authentication protocol for the low-cost RFID system, which is the G-I protocol. They claimed that their protocol provides an efficient mutual authentication. It can defy the well-known attacks and it provides stronger security than these protocols described above. But by analyzing, their protocol cannot prevent tracing attack and de-synchronization attack. We will focus on analyzing the G-I protocol in next section.
4. Review and Analysis of the G-I Protocol
4.1. The G-I Protocol
For the G-I protocol, the tag stores its secret keys and. The backend server/reader stores the secret keys of all tags:, , and their Hash values:,. is the current secret key. is the secret key of the last successful authentication. is a Hash function. The backend server/reader and the tag can implement Hash function and pseudorandom number generating operation. The used symbols in the G-I protocol are listed in Table 1. This protocol is shown in Figure 2 and it is described as follows:
1. The backend server/reader sends a message, , to the tag.
2. After receiving the message, , the tag computes and sends it to the backend server/reader.
3. The backend server/reader tries to look for the received in its database by replacing with and respectively.
In case it is found, the backend server generates a random number and computes, then it sends and to the tag.
4. After the tag receives and it computes. If then it authenticates the backend server/reader. Then the tag generates another random number and computes. The tag sends and to the backend server/reader.
5. The backend server/reader receives and. It computes. If then it authenticates the tag. After completing the authentication to the tag the backend server/reader updates its secrecy as follows:
6. After the backend server/reader has updated its secret keys, it sends “” to the tag. The tag receives “” and it updates its secret keys as follows:
Table 1.The symbols used in the G-I protocol.
Figure 2. The diagram of the G-I protocol.
4.2. The Vulnerability Analysis of the G-I Protocol
Győző Gódor and Sándor Imre claimed that their protocol can resist eavesdropping, replaying, tracing and spoofing. It is very strong against de-synchronization attack and it provides forward and backward security. But by analyzing, it is found that their protocol is vulnerable to de-synchronization attack and tracing attack. The G-I protocol doesn’t provide their claimed security. One reason, which results in the vulnerability of the protocol, is that the protocol cannot keep the freshness of the sessions between backend sever/reader and tag. Another reason is the worse property of exclusive OR operation and the messages, and, are not signed by their sender before they are sent.
In order to enhance the scalability and anonymity of the G-I protocol, is used as a pseudonym to be sent to the backend server/reader so as to declare the identity of the tag. But this makes the protocol vulnerable to tracing attack. The process of tracing attack is described as follows:
(1) The attacker masquerades a legitimate backend server/reader and sends to the tag.
(2) After the tag receives it computes and sends to the attacker.
(3) The attacker blocks the later authentication process or the last step, namely, the attacker prevents “” to be sent to the tag. So the tag cannot update its secret keys.
(4) The attacker masquerades a legitimate backend server/reader again, and sends to the tag.
(5) After the tag receives it will compute and return the same to the attacker.
(6) Repeating the above process, the attacker can locate the tag which sends the same. Therefore tracing attack happens.
The vulnerability of the G-I protocol to tracing attack is that the tag cannot keep the freshness of the sessions which it sends to the backend server/reader. If the tag cannot update its secrecy in time or it does not randomize the response to the backend server/readeran attacker can easily trace it by the fixed.
Győző Gódor and Sándor Imre claimed that their protocol is very strong against de-synchronization attack. But by analyzing, it is found that the G-I protocol cannot resist de-synchronization attack  . An attack scenario is constructed as follows:
(1) The attacker masquerades a legitimate backend server/reader and sends to the tag. Then it gets from the tag.
(2) The attacker masquerades a legitimate tag and sends to the backend server/reader. Then it gets and from the backend server/reader.
(3) The attacker masquerades a legitimate backend server/reader again, and sends and to the tag. Then it gets and from the tag. It keeps, and does not send them to the backend server/reader. The backend server/reader does not update its secret keys because it does not receive and. So its current secret keys are kept. Then the attacker sends the message “” to the tag.
(4) After the tag receives “” from the attacker it begins to update its secret keys as follows:
(5) Later, once the attacker receives from the backend server/reader he masquerades a legitimate tag and replays to the backend server/reader. The backend server/reader can find the matched in its database because its secret keys are not updated. Then it generates, and sends them to the attacker.
(6) The attacker receives and, then it constructs and as follows:
(7) The attacker sends and to the backend server/reader. After the backend server/readerproves that and are legitimate it begins to update its secrecy as follows:
It is obvious that the secrecy between the backend server/reader and the tag are different. De-synchronization attack occurs.
Moreover, there is another simple attack scenario to result in de-synchronization attack for the G-I protocol, which is that an attacker intercepts “” and he does not send it to the tag. Because the tag does not receive “” it cannot update its secret keys, and. But the backend server/reader updates its secret keys, , and. In this case, of the backend server/reader is updated and it is different from of the tag. This makes the protocol cannot complete the later authentication. So de-synchronization attack occurs.
It is a great challenge to design a lightweight authentication protocol which is secure and efficient for the low- cost RFID system. In this paper, we analyze some typical Hash-based lightweight authentication protocols and the G-I protocol, and find these protocols are not as secure as they claimed. For the G-I protocol, we demonstrate that an adversary can trace a tag by repeating to send “” and blocking the later authentication process. An adversary can masquerade a legitimate tag or a backend server/reader to tamper or counterfeit some sessions and to replay them so that the tag and the backend server/reader cannot update their secret keys synchronously. For overcoming the weakness of the RFID authentication protocols, some feasible suggestions are given out:
(1) In order to resist tracing attack, the response of a tag to the backend server/reader must be randomized by a random number, which is generated by the tag. When a tag receives a different query from the backend server/reader it should give a different response. Therefore the freshness of the sessions between tag and backend server/reader is kept so that an adversary cannot distinguish a tag by the intercepted sessions.
(2) In order to resist de-synchronization attack, the tag or the backend server/reader begins to update its secrecy if and only if it successfully implements the authentication to its partner. Otherwise, the tag begins to update its secrecy if and only if the backend server/reader has updated its secrecy. It is avoided for a tag to update its secret keys before the backend server/reader updates its secrecy.
We are appreciated to anonymous reviewers for their constructive suggestion to this paper so that we can improve it. This research work was supported by the National Natural Science Foundation of China under Grant No. 61272097.
 Eetu, P.-S., Karri, R. and Ville, H. (2014) The European Approach to Addressing RFID Privacy. International Journal of Radio Frequency Identification Technology and Applications, 4, 260-271.
 Peris-Lopez, P., Hernandez-Castro, J.C., Estevez-Tapiador, J.M. and Ribagorda, A. (2006) RFID Systems: A Survey on Security Threats and Proposed Solutions. IFIP International Federation for Information Processing 2006 (PWC 2006), 4217, 159-170.
 Dehkordi, M.-H. (2014) Improvement of the Hash-Based RFID Mutual Authentication Protocol. Wireless Personal Communications, 75, 219-232.
 Hermans, J. and Peeters, R. (2014) Proper RFID Privacy: Model and Protocols. IEEE Transactions on Mobile Computing, 13, 2888-2902.
 Weis, S.A., Sarma, S.E., Rivest, R.L. and Engels, D.W. (2003) Security and Privacy Aspects of Low-Cost Radio Frequency Identification Systems. Proc. of the 1st International Conference on Security in Pervasive Computing, Boppard, 12-14 March 2003, 201-212.
 Ohkubo, M., Suzuki, K. and Kinoshita, S. (2004) Hash-Chain Based Forward Secure Privacy Protection Scheme for Low-Cost RFID. Proc. of the 2004 Symposium on Cryptography and Information Security, Sendai, 27-30 January 2004, 719-724.
 Yeo, S.-S. and Kim, S.-K. (2005) Scalable and Flexible Privacy Protection Scheme for RFID Systems. European Workshop on Security and Privacy in Ad Hoc and Sensor Networks ESAS’05, Visegrad, 13-14 July 2005, 153-163.
 Cho, J.-S., Jeong, Y.-S. and Sang, O.P. (2012) Consideration on the Brute-Force Attack Cost and Retrieval Cost: A Hash-Based Radio-Frequency Identification (RFID) Tag Mutual Authentication Protocol. Computers and Mathematics with Applications, 3, 1-8.
 Khedr, W.I. (2013) SRFID: A Hash-Based Secure Scheme for Low Cost RFID Systems. Egyptian Informatics Journal, 14, 89-98.
 Safkhani, M., Peris-Lopez, P., Hernandez-Castro, J.C. and Bagheri, N. (2014) Cryptanalysis of the Cho et al. Protocol: A Hash-Based RFID Tag Mutual Authentication Protocol. Journal of Computational and Applied Mathematics, 259, 571-577.
 Ha, J.H., Moon, S.J., Zhou, J.Y. and Ha, J.C. (2008) A New Formal Proof Model for RFID Location Privacy. Proc. of the 13th European Symposium on Research in Computer Security—ESORICS’08, Malaya, 6-8 October 2008, 267-281.
 Sun, D.-Z. and Zhong, J.-D. (2012) A Hash-Based RFID Security Protocol for Strong Privacy Protection. IEEE Transactions on Consumer Electronics, 58, 1246-1252.